<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Stanko Jankovic on Medium]]></title>
        <description><![CDATA[Stories by Stanko Jankovic on Medium]]></description>
        <link>https://medium.com/@stankoja?source=rss-90b6c24d5272------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*F89ziEHheP2N_3nE.jpg</url>
            <title>Stories by Stanko Jankovic on Medium</title>
            <link>https://medium.com/@stankoja?source=rss-90b6c24d5272------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 10:46:12 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@stankoja/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[The 10 Puzzle Pieces of Neuroevolution]]></title>
            <link>https://medium.com/@stankoja/the-10-puzzle-pieces-of-neuroevolution-b88a170f3573?source=rss-90b6c24d5272------2</link>
            <guid isPermaLink="false">https://medium.com/p/b88a170f3573</guid>
            <category><![CDATA[neuroevolution]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[evolution]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Stanko Jankovic]]></dc:creator>
            <pubDate>Tue, 27 Aug 2024 21:10:16 GMT</pubDate>
            <atom:updated>2024-08-27T21:10:16.877Z</atom:updated>
            <content:encoded><![CDATA[<p>Our brains are proof that evolution works, and that it can develop extremely complex systems at scale. But digital neuroevolution algorithms are not even getting close to the real thing. What puzzle pieces are we missing? Or have we got them all, but just have to figure out how everything fits together? Maybe some of the pieces are redundant or superfluous? In this post, I want to explore the puzzle pieces that we have on the table today.</p><h4>#1 Mutations</h4><p>Mutations are essential for evolution. Imagine a bacteria that became immune to mutations. It could clone itself perfectly, but that would mean it could not change, could not evolve. Mutations are errors that occur while copying genetic code. With digital neuroevolution, many algorithms will perform mutations on the neural network directly, like adding neurons, updating weights. But in real life, mutations happen on a much lower level. Such mutations just randomly change raw “bytes” (like deletions, point mutations, duplications, translocations etc) without awareness of what the code represents at higher level. An important factor here is the rate of mutation. We need to get that rate just right for evolution to work. Too many or too few mutations could get us stuck. If we could add the mutation rate as an evolvable parameter, then the mutation rate could dynamically adjust as needed (like a dynamic learning rate).</p><h4>#2 Genome</h4><p>The genome is basically the codebase. Evolution constantly makes changes to it in hope for producing a better version. All higher level features of an organism are represented in the codebase, but in an indirect lower level encoded form. The DNA of all life forms on earth encodes information in the same way. It may not seem that important how information is encoded, but that only the content that is encoded counts. But could the encoding be the key for why evolution can make code changes at such a scale? Maybe it’s thanks to the encoding that the mutations do not impact the codebase too significantly, but just enough to drive positive changes. Maybe code reuse or constraints that limit the search space in a constructive way could be encouraged with a good encoding strategy too?</p><h4>#3 Parser</h4><p>But what would the genome encoding mean without an algorithm to parse it? It would be just a string of random characters. Digital neuroevolution does not pay much tribute to the parsing algorithm, because doesn’t the way we encoded the genome determine what the parsing algorithm should be? Aren’t the encoding and the parsing algorithm just two sides of the same coin? That may be true if we just want to hardcode the encoding, but if we want to allow the encoding to evolve, we may need to rethink our approach. In real life, DNA is parsed by ribosomes, which are responsible for processing the information that is encoded in the DNA. So we end up with a seemingly paradoxical situation where the DNA information encodes all building block of our bodies, including ribosomes, but to read that information, we need ribosomes. The DNA encoding and ribosomes must have evolved in some kind of tandem evolutionary dance, and were not hardcoded as in digital neuroevolution. This reminds me a bit of the short-story “Library of Babel” by Jorge Luis Borges, where the universe is a library that contains a seemingly infinite number of books, with all possible combinations of the characters in the alphabet. But despite that, there was no book that did not have a meaning, because for every book that contained gibberish, there was another book that described how to decode that gibberish.</p><h4>#4 Neurons</h4><p>In real life, DNA will define all aspects on how an organism will work, down to celular or atomic level. In digital neuroevolution, we generally limit the end product, which is the output of the parser, to just a neural network. That means, capabilities of neurons are predefined, and we only evolve its weights and connections (network structure). Although that’s a limitation we need to accept, being aware of its impact to the performance of the neural network is important. Neurons that can learn during their lifespan, or neurons that provide oscillator output without having any input could be some helpful extra building blocks.</p><h4>#5 Input / Output</h4><p>When speaking about evolving the structure of artificial neural networks, we usually mean evolving the hidden layers of the neural network. The input and output layers are always defined by the problem the neural network is supposed to solve. But that approach seems to run into scaling issues, especially as the number of inputs or outputs grows. And that is not a surprise. In real life, inputs and outputs evolved gradually. If we take the eye as an example, it did not suddenly appear with millions of sensors. It started as a singe light sensitive cell, and over time the number of such cells increased gradually. To make neuroevolution of the structure of artificial neural networks scale, we will need to come up with a way to grow not just the hidden layers gradually, but also the inputs and outputs. But that is harder than it seems. Let’s say we want a neural network to process images of 1 megapixel. If we start with a single input, what should that input be? Assigning the input to a random pixel would likely not be of much use, but assigning the input to some average value calculated based on all pixels in the image would be more in line to what an organism with a single light sensitive cell would experience. That means we need to put in some thought in how we grow the inputs and outputs.</p><h4>#6 Crossover</h4><p>Besides mutations, there is another code reuse trick that evolution came up with: crossover. During sexual reproduction, the genes of two individuals are mixed up. Each individual inherits a set of genes from one parent, and a set of the same genes (but different versions) from the other parent. Since every individual has 2 versions of each gene (one from the father and one from the mother), there are processes to determine which gene will be active, and which one will be passive. The passive genes do not contribute in any way to the current individual, but could still be passed to the next generation. When an individual passes genes to the next generation, it can‘t pass both versions of each gene, but only one (either the one inherited from the father or the one inherited from the mother). A process called crossover occurs to select which version of each gene will be passed. That means, mixing of genes occurs at two stages. The first one is the crossover process that happens in the parent to select which version of each gene should be passed on, and the second one happens in the child to select which of the two inherited gene versions (one from father and the other from the mother) will be active, and which passive. Thanks to this process, the same beneficial property does not have to evolve in each organism separately, but the code can be shared among individuals. One of the main challenges of neuroevolution is how to ensure that parts of code that are shared this way are compatible. In real life, on a higher level, organisms have evolved to search for partners who are likely to have the best quality and most compatible code. On a lower level, genes are arranged in alleles which helps identify alternate versions of the same code.</p><h4>#7 Selection</h4><p>Selection is probably the first thing that comes to our mind when talking about evolution. The role of selection is to find an efficient way to search the evolutionary tree (or gradient). We need to come up with a way to explore branches that are likely to lead to improved fitness, and to spend less time exploring branches that are likely dead ends. The solution to this problem nature has come up with sounds rather simple: only the fittest individuals can carry their genes into their next generation. But since genes of all individuals in the next generation get re-shuffled, we could get into a situation that all individuals in the new generation are worse than the best individuals of the previous generation. To avoid that problem, we could apply a slightly un-natural selection approach, where we carry over a certain number of fittest individuals into the next generation unchanged, and fill the rest of the generation the usual way by shuffling genes of the fittest individuals. But focusing always on the fittest might lead to problems too because in some cases individuals may stagnate for a while until enough changes accumulate to something positive. A Monte Carlo tree search approach could help look ahead and estimate which branch to explore, but it will introduce additional hyperparameters that we need to tune. There are many tradeoffs to account for, and even though selection appears simple, it’s one of the more complex puzzle pieces of evolution because of the many strategies that could be used to explore the evolutionary tree.</p><h4>#8 Speciation</h4><p>Some evolutionary algorithms will during the selection phase split the population into species, and will ensure that genes of best individuals from each species get carried over to the next generation. This leads to more diversity in the population. The goal is to avoid getting stuck in a local minima, but to allow the algorithm to explore different parts of the evolutionary gradient. Another benefit of speciation is to allow less fit individuals to survive long enough to accumulate changes which could lead to increased fitness in the long run. When evolving only the weights of a neural network with fixed architecture, speciation would not be needed because we could just re-start the evolution with new random initial parameters when we believe we are stuck in a local minimum. But when evolving the architecture too, this might not be the best approach, and a solid speciation strategy might be more efficient. Having an environment that would encourage development and survival of multiple species might be a better approach than manually implementing such constraints.</p><h4>#9 The environment</h4><p>A simple environment will likely not lead to complex brains, because brains will evolve only as much as the environment is challenging them. On the other hand, starting with challenges that are too complex will present a learning curve that is too steep for evolution to climb. That means that the challenges need to be gradual, and the environment dynamic enough to always offer an opportunity that is in reach for evolution to make progress. Incorporating the population itself into the environment could be one approach to introduce some dynamic change into the environment. As more complex brains evolve, the more complex their impact on the environment and on the rest of the population.</p><h4>#10 Constraints</h4><p>To further narrow down the search space, we could always add some manual constraints to how brains could be structured. For example, we could add the notion of physical space, to ensure that neurons prefer to connect to physically closer (and possibly logically more relevant) neurons. That would also apply to input and output neurons, because neurons connecting to same sensor types (e.g. visual) should probably connect to same internal neural structures. That may not be that important in the beginning while the brain has a small number of neurons, but can become crucial in later stages as the number of neurons grow. Applying such constraints would require neurons to have additional attributes that define their location in space. In real life, such constraints are dictated by the environment. That means, the same constraints (physical laws) apply to the external world in which the individual lives, and to the processes that determine how brains develop. In digital neuroevolution, those rules are usually separated, and the environment has only a set of rules about what an individual can do, but the brain development is controlled by a completely separate set of rules.</p><h4>Conclusion</h4><p>Evolution has created complex minds in real life, so why should the same not be possible with digital neuroevolution? Evolution in real life is not just evolving neural networks, it’s evolving whole organisms, and it was evolving complex molecules before that, and maybe it’s evolution all the way down. That is how evolution got all puzzle pieces right. It showed what is possible, and we just need to get the puzzle pieces together to do the same.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b88a170f3573" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Neuroevolution — The current state]]></title>
            <link>https://medium.com/@stankoja/neuroevolution-the-current-state-58be2778c8d4?source=rss-90b6c24d5272------2</link>
            <guid isPermaLink="false">https://medium.com/p/58be2778c8d4</guid>
            <category><![CDATA[evolution]]></category>
            <category><![CDATA[intelligence]]></category>
            <category><![CDATA[neuroevolution]]></category>
            <category><![CDATA[ai]]></category>
            <dc:creator><![CDATA[Stanko Jankovic]]></dc:creator>
            <pubDate>Wed, 14 Aug 2024 21:32:53 GMT</pubDate>
            <atom:updated>2024-08-14T21:32:53.953Z</atom:updated>
            <content:encoded><![CDATA[<h3>Neuroevolution — The current state</h3><p><em>The earliest form of natural selection was simply a selection of stable forms and a rejection of unstable ones. </em>— Richard Dawkins, The Selfish Gene</p><p>The majority of modern artificial neural networks are trained using backpropagation. An alternative would be to use neuroevolution, but that approach apparently does not scale very well.</p><p>But how comes that evolution has created complex minds in the real world not just once, but multiple times almost independently? Take for example the octopus, whose mind evolved almost independently of the one belonging to mammals.</p><p>We need to be clear that neuroevolution algorithms that are used to train artificial neural networks are not evolving the whole organism, but just the neural networks. Can we really apply evolution in such a way and ignore everything except the neural network? That might work for smaller neural networks, but we will encounter scaling issues when trying to train larger neural networks. But evolution did not train our brains from scratch. Our brains evolved from smaller brains, and those evolved from even smaller brains (and with lower number of inputs/outputs). That is something we need to keep in mind when training large neural networks using neuroevolution. The environment is another important ingredient. It needs to support the evolution of simple minds, but also be flexible enough to encourage the growth of more complex minds. It’s not enough for the environment to be just dynamic, but it must be changing in the right way to support more complex minds to evolve in a gradual way. And a key component of the environment are other organisms that are shaping it.</p><p>There may be many other secrets we need to uncover before we can use evolution to our benefit. Mutations are a key component of the evolutionary algorithm, but those happen rather indirectly through changes in DNA. The way DNA is encoded allows mutations to happen, not too frequently, and also not to rarely, but just in the right amount and in the right way to allow organisms to evolve. Can the encoding of DNA also have impact on the ratio of good vs bad mutations? Mixing of genes during reproduction is another important ingredient that allows one organism to combine it’s good genes with good genes that evolved in a different organism. And at the end, what is the best way to explore the tree of evolutions, or in other words, how are the fittest organisms selected?</p><p>There is a lot to explore. To better understand where we are, and what we might be missing, I’d like to start exploring what neuroevolution algorithms have been created so far.</p><p>The Wikipedia page for Neuroevolution lists 15 algorithms, so I’ll start with exploring those.</p><p><strong>Neuro-genetic evolution by E. Ronald, 1994</strong> (<a href="https://inria.hal.science/hal-01079614/document">https://inria.hal.science/hal-01079614/document</a>) — The paper is about a basic genetic algorithm for evolving weights in a neural network with static pre-defined architecture. Fittest individuals are selected and the weights are directly mutated or crossed over between individuals to create the next generation. The main focus of the paper is the impact of normalization of input data on the training results, with the conclusion that different input normalization may be suitable for different problems, and that the normalization coefficient should ideally be a learnable parameter.</p><p><strong>Cellular Encoding (CE) by F. Gruau, 1994</strong> (<a href="https://www.academia.edu/81718267/Neural_Network_Synthesis_using_Cellular_Encoding_and_the_Genetic_Algorithm">https://www.academia.edu/81718267/Neural_Network_Synthesis_using_Cellular_Encoding_and_the_Genetic_Algorithm</a>) — The focus of this lengthy paper (150+ pages) is on encoding neural networks using a grammar approach. That is in contrast to direct encoding where the neural network is defined explicitly in detail, and also in contrast with parameter based encoding where the hyperparameters like number of layers or neurons is defined, and the network is generated based on that. Modularity is another important topic of the paper and the approach taken here is to represent the neural network in form of a grammer tree, where sub-trees could be used to achieve modularity. The problem of crossing over is also brought up because “cross-over directly on the hardware of the connections can produce non-functional offsprings. It is known as the structural/functional problem. The solution is to encode on the chromosome a collection of abstract features more likely to provide building blocks. There must be some abstraction in the representation”. In the end, crossover is achieved by cutting a sub-tree from the parent tree and replacing it with a subtree from the other parent. Another interesting approach used in the paper is to use information theory for creating the loss function instead of the usual mean square error.</p><p><strong>GNARL by Angeline et al., 1994</strong> (<a href="http://www.demo.cs.brandeis.edu/papers/ieeenn.pdf">http://www.demo.cs.brandeis.edu/papers/ieeenn.pdf</a>) — GNARL is an evolutionary algorithm that is used to acquire both network topology and wight. It’s focus is on removing as many restrictions to the topology formation as possible, like allowing recurrent corrections. The number of input and output modes is fixed, as defined by the problem to be solved, and some other parameters like maximum number of hidden neurons are fixed too. The rate of mutation depends on the fitness of the individual, i.e. less fit individual are mutated more than those that are fitter. That helps prevent getting stuck in local minima (similar to a flexible learning rate).</p><p><strong>EPNet by Yao and Liu, 1997</strong> (<a href="https://www.cs.bham.ac.uk/~axk/evoNN2.pdf">https://www.cs.bham.ac.uk/~axk/evoNN2.pdf</a>) — Both network architecture and weights are evolved using this approach. Direct endocing is used. EPNet uses a hybrid approach of evolutionary algorithms and backpropagation training. The network is trained using backpropagation after each architectural mutation to ensure that the weights are optimal before attempting the next architectural mutation. The parsimony of evolved ANN’s is encouraged by preferring node/connection deletion to addition. In order to reduce the detrimental effect of the permutation problem, an EP algorithm, which does not use crossover, is adopted in EPNet. Genetic algorithms use crossover and mutation to search the evolution space of possible solutions. Evolutionary programming uses primarily mutation. Node addition is implemented through splitting an existing hidden node, a process called “cell division”. The evolution simulated by EPNet is closer to the Lamarckian evolution than to the Darwinian one.</p><p><strong>NeuroEvolution of Augmenting Topologies (NEAT) by Stanley and Miikkulainen, 2002</strong> (<a href="https://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf">https://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</a>) — NEAT is currently one of the most popular genetic algorithms. It uses an approach of assigning IDs to connections, and that information is then used for better crossover performance (to ensure gene are crossed over with right genes) and speciation (to allow non-optimal solutions time to evolve instead of immediately discarding them). Whenever a new gene appears (through structural mutation), a global innovation number is incremented and assigned to that gene. NEAT starts growing a network from scratch, meaning without any hidden neurons. That approach allows it to get to the optimal solution faster, without using more neurons than necessary. The authors compare that with incremental evolution (Gomez and Miikkulainen, 1997; Wieland, 1991), but instead having to manually train the network on more difficult tasks, adding structure to the network achieves the same goal, but in an automated way. Direct encoding of the genome is used “because indirect encodings do not map directly to their phenotypes, they can bias the search in unpredictable ways. To make good use of indirect encodings, we need to first understand them well enough to make sure that they do not focus the search on some suboptimal class of topologies”. As with all GAs, scaling is a problem here too. Possible reasons are lack of code reuse approaches that scale, and lack of growing number of I/O.</p><p><strong>Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT) by Stanley, D’Ambrosio, Gauci, 2008</strong> (<a href="https://axon.cs.byu.edu/~dan/778/papers/NeuroEvolution/stanley3**.pdf">https://axon.cs.byu.edu/~dan/778/papers/NeuroEvolution/stanley3**.pdf</a>) — It took me some time to understand the general idea, but in a nutshell HyperNEAT uses NEAT to evolve a neural network (a Compositional Pattern Producing Network — CPPN) which has the only purpose to predict the weight in a second neural network with a fixed topology. That second neural network is the actual neural network that is used for solving the final problem, and whose fitness is assessed. To predict weights, the CPPN takes the position of the nodes in the second neural network as input, which can result in certain spatial patterns of weights in the second neural network. This means that we are encoding the second neural network weights indirectly using the CPPN, which can result in more efficient evolutionary training since the CPPN is generally smaller and has lower number of dimensions than the second/main network. By factoring in node spatial positions (especially input and output geometry) into connection weights, we are providing some additional spatial information to the neural network that would not be easily available to neural networks evolved using regular NEAT.</p><p><strong>Evolvable Substrate Hypercube-based NeuroEvolution of Augmenting Topologies (ES-HyperNEAT) by Risi, Stanley 2012</strong> (<a href="https://direct.mit.edu/artl/article/18/4/331/2720/An-Enhanced-Hypercube-Based-Encoding-for-Evolving">https://direct.mit.edu/artl/article/18/4/331/2720/An-Enhanced-Hypercube-Based-Encoding-for-Evolving</a>) — In contrast to HyperNEAT where the neuron topology is fixed, ES-HyperNEAT will determine position and desnsity of neurons dynamically.</p><p><strong>Evolutionary Acquisition of Neural Topologies (EANT/EANT2) by Kassahun and Sommer, 2005 / Siebel and Sommer, 2007</strong> (<a href="https://www.informatik.uni-kiel.de/inf/Sommer/doc/Projekte/yk/ESANN2005EANT.pdf">https://www.informatik.uni-kiel.de/inf/Sommer/doc/Projekte/yk/ESANN2005EANT.pdf</a>, <a href="https://www.informatik.uni-kiel.de/inf/Sommer/doc/Publications/nts/SiebelSommer-IJHIS2007.pdf">https://www.informatik.uni-kiel.de/inf/Sommer/doc/Publications/nts/SiebelSommer-IJHIS2007.pdf</a>) — EANT is using a “kind of” direct encoding to encode neurons and connections in a linear genome. The topology of the netowrk is determined by the ordering of the genes in the genome. The linear genome can be parsed directly without decoding it to process the neural network. The neural network encoded this way is shaped into layers, but it is possible to have both forward and recurrent connections between layers. EANT2 was developed to allow evolving of network topology too.</p><p><strong>Interactively Constrained Neuro-Evolution (ICONE) by Rempis, 2012</strong> (<a href="https://osnadocs.ub.uni-osnabrueck.de/bitstream/urn:nbn:de:gbv:700-2012101710370/3/thesis_rempis.pdf">https://osnadocs.ub.uni-osnabrueck.de/bitstream/urn:nbn:de:gbv:700-2012101710370/3/thesis_rempis.pdf</a>) — ICONE is described in a 240 page phd dissertation. It has the goal to improve evolution of mid-scale neural networks by scaling the evolution process better. To. do that, it applies certain constraints to the evolution process so that the search space is narrowed down to a particular problem domain. One approach to apply such constraints is to group neuraons in groups/modules and limit which neurons inside the module can connect to neurons outside it. That not only narrows down the search space, but also allows a kind of code reuse and makes crossover possible. The constraints are not just passive, but can enforce for example symmetries by adjusting the network to ensure all new mutations are present in a symetric way. That greatly speeds up evolution of neural network where symmetries are beneficial (e.g. in case of symmetric bodies). There are numerous other constrains, e.g. to restrict number of neurons, connection density, or constraints to ensure local connections a are prefered to more remote connections (to avoid connecting to unrelated parts of the network). All the mentioned modularization and constraints need to be set up manually with domain knowledge about the problem to be solved.</p><p><strong>Deus Ex Neural Network (DXNN) by Gene Sher, 2012</strong> (<a href="https://arxiv.org/pdf/1111.5892">https://arxiv.org/pdf/1111.5892</a>) — The linked paper is not the original DXNN paper, but it’s some related paper about practical applications of DXNN written by the same author. DXNN separates the evolution of the topology and the evolution of the weights into two phases. That is done to ensure that evolved topologies are not discarded immediately, but that optimal weights are identified first, to allow proper evaluation of the topology fitness. To generate weights, DXNN uses a similar approach as HyperNEAT, but besides providing just the connection/node coordinates as inputs to the CPPN, it provides several other parameters aswell. To better scale the evolution process, the DXNN algorithm allows during the mutation phase not just manipulation of the internal neural structure, but also adding sensors/actuators over time. That way, sensors/actuators can be incorporated over time, which will allow better scaling of the neural network evolution.</p><p><strong>Spectrum-diverse Unified Neuroevolution Architecture (SUNA) by Danilo Vasconcellos Vargas, Junichi Murata</strong> (<a href="https://arxiv.org/pdf/1902.06703#:~:text=The%20combination%20of%20Spectrum%20Diversity,five%20classes%20of%20problems%20tested">https://arxiv.org/pdf/1902.06703</a>) — The main innovations introduced with this algorithm are new types of neurons (like control neurons that have a control input to allow them to be turned off/on, or neurons that have different activation speeds) and a new approach to speciation. Do group entities into species, this algorithm uses an approach that reminds of spectrum analysis of materials (hence it’s name). That means, it will use properties of the genome like number of neurons, number of certain types of activation functios etc. to calculate a spectrum of the genome. Genomes are then grouped into species based on their spectrum.</p><p><strong>Modular Agent-Based Evolver (MABE) by Clifford Bohm, Arend Hintze, and others</strong> (<a href="https://direct.mit.edu/isal/proceedings/ecal2017/29/76/99520">https://direct.mit.edu/isal/proceedings/ecal2017/29/76/99520</a>) — MABE is not an evolutionalry model, but a modular toolbox for testing out different evolutionary strategies. It allows swapping modules like different brain types, or different genome types to speed up testing of a hypothesis.</p><p><strong>Covariance Matrix Adaptation with Hypervolume Sorted Adaptive Grid Algorithm (CMA-HAGA) by Shahin Rostami, and others.</strong> (<a href="https://eprints.bournemouth.ac.uk/24371/1/CMAPAES-HAGA.pdf">https://eprints.bournemouth.ac.uk/24371/1/CMAPAES-HAGA.pdf</a>) — The paper describes an evolutionary algorithm for optimizing problems that have many objectives. The main issue with multi objective problems is the curse of dimensionality, meaning that it becomes difficult to compare different solutions across all problems. This algorithms demonstrated better performance compared to some other algorithms.</p><p><strong>GACNN (</strong><a href="https://arxiv.org/pdf/1909.13354">https://arxiv.org/pdf/1909.13354</a>)— This algorithm is specific to evolving Convolutional Neural networks. It tries to explore training convolutional neural networks using an evolutionary approach rather than using backpropagation. It uses an encoding method that reduces the genome size. Different selection strategies are offered, like “steady-state” where individuals are replaced with better ones, “generational” where the new generation is created by crossing over and mutating best individuals from current generation, and “elitist” where a certain number of fittest individuals are carried over unchanged into the new generation, and the rest of the population is generated using crossover/mutations. When comparing these three selection methods, it was determined that the “stead-state” ensures a stead increase of overall fitness, without the risk of drops in fitness, but the progress ca be rather slow and it can get stuck in local optima. The “generational” approach is much faster and explores a much wider solution space, but its progress tends to fluctuate and the overall fitness can also drop. The “elitist” apprach turned out to be the best because it has the characteristics of both the “steady-state” and the “generational” approach, meaning that it shows a more steady progress, but still manages to explore a wider solution space. When comparing the “elitist” approach with classical backpropagation, it usually shows better results in the initial phases of training, but in the end it still falls short.</p><p><strong>Fast-DENSER by Assunção et al and others</strong> (<a href="https://arxiv.org/pdf/1905.02969">https://arxiv.org/pdf/1905.02969</a>) — This algorithm, which uses indirect grammer encoding to represent the genome, can be used to train structure, weights, but also evolutionary hyperparameters. That means, instead of training all individuals for a certain number of epoch, the training time can be dynamic, so that in the end of evolution we end up with a fully trained network that does not need further training.</p><p>I’m sure there are many more papers on Neuroevolution out there, besides those listed on the Wiki page. But even the 15 mentioned in this article clearly demonstrate that Neuroevolution is a complex topic, and that there are so many things to tune to get it right. In the end, we have not got it right yet. All algorithms suffer from scaling problems. Rather than solving simple pole balancing problems and showing marginal gains compared to other algorithms, I believe we need to aim higher. But that would be a topic for another blog post.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=58be2778c8d4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How hard is the hard problem of consciousness?]]></title>
            <link>https://medium.com/@stankoja/how-hard-is-the-hard-problem-of-consciousness-e19d900a0910?source=rss-90b6c24d5272------2</link>
            <guid isPermaLink="false">https://medium.com/p/e19d900a0910</guid>
            <category><![CDATA[conciousness]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Stanko Jankovic]]></dc:creator>
            <pubDate>Fri, 06 Oct 2023 20:55:12 GMT</pubDate>
            <atom:updated>2023-10-06T20:55:12.206Z</atom:updated>
            <content:encoded><![CDATA[<p><em>“This line of thought expressed in speech is not extended in space at all, but comes towards me like carriages in a goods train, one after the other, coming out of the darkness, passing under the floodlight of knowledge, and receding into memory.”</em> — John M Hull, Touching the Rock</p><p>Modelling the human thought process is the holy grail of AI, and we are still in a stage where we are not even sure if that is possible or not. Some will argue that the mind is more than a computation. How else can we see truth like the one in Gödel’s theorem when there is no mathematical proof for it? Others will say that Gödel’s theorem has that strange property only because it is self referencing, and that we can see the truth because our thought process is self referencing too.</p><p>But even if we manage to model our thought process artificially, how will we know that the AI will experience the world the way we do. Can we model the experience of seeing the color red? It seems that we can’t break that problem down further, and it’s the same no matter what experience we take. I can’t explain the feeling of seeing red to you. I can just ask “do you know what I mean by that feeling?” Experiences are just there.</p><p>Pan-psichysist say that modeling the human thought process and modeling the way humans experience the world are two different problems. According to them, even if we manage to model the human thought process, we will not necessarily be able to make robots feel, because experiences (e.g. the experience of the color red) are fundamental properties of the universe and are not a product of computation. Experiences are just there, as if hidden by some impenetrable layer of abstraction, and our mind has some way to access them.</p><p>But if the property of experiences is that they are just there, hidden behind some layer of abstraction, do we really need to hide them behind the fundamental layers of the universe? Can’t we just hide them behind layers of abstraction in our own brain? Our thought process is at a higher level of abstraction, unaware of the neuron firings that produce it. Like built-in functions of some higher level programming language that are just there, but under the hood, those are implemented in a lower level code behind a layer of abstraction. There is a whole “universe” of subconscious activities going on at lower levels of our mind, down to the neuron level, and those may serve things to our conscious mind that end up just being there. As if they are a fundamental property of the universe, and not a fabrication of our own mind.</p><p>And this is a key problem. Philosophy alone will not allow us to penetrate these layers of abstraction. Neurology research like that which uncovered the architecture of the visual cortex, and the work done by AI researchers to model such neural architectures digitally are the right path forward. That approach will allow us to break the problem down into smaller chunks and test them out using AI models. But in the end, I’m not sure if this philosophical blog post is contradicting itself, or if it’s just a Gödelian self reference.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e19d900a0910" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The two ways of implementing backpropagation]]></title>
            <link>https://medium.com/@stankoja/the-two-ways-of-implementing-backpropagation-f839bf7f3fe2?source=rss-90b6c24d5272------2</link>
            <guid isPermaLink="false">https://medium.com/p/f839bf7f3fe2</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[backpropagation]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Stanko Jankovic]]></dc:creator>
            <pubDate>Tue, 27 Dec 2022 22:07:14 GMT</pubDate>
            <atom:updated>2022-12-27T22:07:14.918Z</atom:updated>
            <content:encoded><![CDATA[<p>I went through plenty of blog posts, videos and books explaining how neural networks work and how to code them from scratch. Although I finally understood all the details and the math (to some degree I guess 😅), there was one step in the backpropagation process that confused me the most, and the main reason for that is not the calculus, but that it was implemented differently in different tutorials.</p><p>I’m not going to explain the whole backpropagation process, but I’ll briefly outline the main steps so that we can narrow down the part I mentioned. I have included a sketch of a simple neural network below to help us visualize the process (we are ignoring the bias in this case for sake of simplicity). It consists of an input layer, a hidden layer, and an output layer, each containing 2 neurons.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*BgnhpXJ-WLoutp1N86bkAg.png" /><figcaption>Figure 1: Sample neural netwrok</figcaption></figure><p>Usually, the steps for training the network using backpropagation are as following:</p><ol><li>We first do a forward pass through the network, and save the outputs of each network layer, including the outputs of the hidden layer(s).</li><li>We calculate the output errors of the final layer using an error function (e.g. Mean Square Error — MSE).</li><li>Using calculus and the chain rule, we calculate how much we need to update the weights of the last hidden layer (in this case the blue weights).</li><li>We repeat step 3 for weights of each previous layer (in this case the orange weights)</li></ol><p>Step 1 and 2 are pretty straightforward. Step 3 requires some calculus, but once that math is mastered, its pretty straightforward too. In summary, we need to calculate the derivative of the output error function in respect to the weights of the last hidden layer (blue). That will help us figure out how much to nudge each weigh between layer 2 and layer 3 in order to reduce the error.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/412/0*UDICtbZb8LC7d3aY" /><figcaption>Figure 2: The derivative of the output error function in respect to the weights before the output layer. On the right side is the chain rule that helps us calculate the derivative, but I won’t go into the calculus here.</figcaption></figure><p>So far so good. But step 4 is where things got a bit complicated, and that step was implemented in different ways in different tutorials.</p><p>The first way I saw it implemented is to simply use calculus and the chain rule again, as in step 3, but instead of calculating the derivative of the output error function in respect to the blue weights between the hidden and the output layer, we calculate the the derivative of the output error function in respect to the orange weights between the input and the hidden layer. The calculus chain rule allows us to do that.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/539/0*gTt5Aj-ER_nXiDkB" /><figcaption>Figure 3: Here we are using the chain rule again to calculate how changes in the orange weights impact the output errors of the network. If the network had more layers, we could continue expanding the chain rule this way.</figcaption></figure><p>The second way I saw it implemented is to not use the output error function, but the error function of the hidden layer (blue layer in this case). But wait, that layer does not have an error function!? How can we calculate the error of a hidden layer if we do not have a target value for it? The solution is to simply estimate its error by looking at how much that node contributed to the final errors. E.g. if the hidden node is connected to two output nodes like the H₁ node is connected to E₁ and E₂ in the example network below with final errors of 2 and 5, and the weights of those connections are 0.1 and 0.2, then the estimated error of that hidden node H₁ is (2 * 0.1) + (5 * 0.2) = 1.2 (or we can square that if we want to use MSE).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/706/1*v7sg46FTxGlhLKISvYJP4w.png" /><figcaption>Figure 4: Estimating error of hidden layer</figcaption></figure><p>Once we have the error of the hidden node, we can use calculus again, like in step 3, to calculate the derivative of that error function in respect to the weights that are right before that hidden layer. In this case, it would be something like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/405/0*cWmzT7Bo4XR4X3X4" /><figcaption>Figure 5: Calculating the derivative of the hidden layer output error function</figcaption></figure><p>This second way sounds a bit more complex, but it may simplify the calculus a bit. In the book “<a href="https://www.amazon.com/Make-Your-Own-Neural-Network/dp/1530826608">Make your own neural network</a>” by <a href="https://github.com/makeyourownneuralnetwork">Tariq Rashid</a>, backpropagation was implemented this way, and you can see that in the <a href="https://github.com/makeyourownneuralnetwork/makeyourownneuralnetwork/blob/master/part2_neural_network_mnist_data.ipynb">source code</a> of that implementation.</p><p>I was wondering if I can modify that code to use the first way of updating weights, which does not require calculating the error of the hidden layers, and that code can be accessed here: <a href="https://github.com/stankoj/neural">https://github.com/stankoj/neural</a>. I won’t go into the details how it works and the calculus to get to that formula, but I can do it in a separate blog post if there is interest in that. But something I can’t answer is which approach is better, and I would appreciate if someone with more experience on this topic would provide some insights into that. I did test both approaches on the MNIST dataset with same hyperparameters and same initial random seeds, and I was usually getting around 1% better accuracy using the second approach (which includes estimating error of hidden layers). But this is just a beginners perspective, and I would appreciate further insights into this and help correcting my errors (please be my error function 😁).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f839bf7f3fe2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[V8 Bug Hunting Part 2: Memory representation of JS types]]></title>
            <link>https://medium.com/@stankoja/v8-bug-hunting-part-2-memory-representation-of-js-types-ea37571276b8?source=rss-90b6c24d5272------2</link>
            <guid isPermaLink="false">https://medium.com/p/ea37571276b8</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[bug-bounty]]></category>
            <category><![CDATA[v8]]></category>
            <dc:creator><![CDATA[Stanko Jankovic]]></dc:creator>
            <pubDate>Sun, 09 Jun 2019 19:36:26 GMT</pubDate>
            <atom:updated>2019-12-27T19:04:53.327Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Disclaimer: This is not really a write-up, but it’s just me taking notes. The content may chaotic, wrong or there may be better ways to do things. If you notice that, please point it out.</em></p><p>&lt;&lt;&lt; <a href="https://medium.com/@stankoja/v8-bug-hunting-part-1-setting-up-the-debug-environment-7ef34dc6f2de">V8 Bug Hunting Part 1: Setting up the debug environment</a></p><h4>Intro</h4><p>After setting up the debug environment, I was ready to play around with V8. The first thing I wanted to look at is how various JS types are represented in memory. JS types are split into two main categories: primitive types (i.e. numbers, strings, boolean…) and objects. We’ll have a look at both categories.</p><h4>Numbers</h4><p>In JavaScript, all numbers are doubles (64 bit floats), which is the “number” primitive type. That’s what the specs tells us. But how does V8 implement them? In most cases, when using numbers in our code, we just use integers. We could just represent them as floats, but wouldn’t it be wasteful?</p><p>Let’s first have a look at a screenshot from my previous blog post:</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*X9BbacHDCkkE8t3pRycjzw.png" /></figure><p>There I have created an array like a=[1,2,3,4,5,6,7,8,9] and have identified it in memory. I have selected what I believed is the integer 2 from the array. I thought that would make sense considering that I’m on a 64 bit system and that memory is little-endian.</p><p>And although in C terms that may make sense, this is not how higher level languages like JavaScript work. JavaScript is a <a href="https://android.jlelse.eu/magic-lies-here-statically-typed-vs-dynamically-typed-languages-d151c7f95e2b">dynamically typed</a> language, which means a variable can contain any type, and in order to be able to do that, JavaScript needs to store some type information with the variable.</p><p>JavaScript Core (WebKit JS engine) uses <strong>NaN-boxing</strong> to store both type information and variable value inside a 64-bit float. V8 uses <strong>tagged pointers</strong> to do that. Because of how memory is aligned, pointers usually point to memory locations that are multiples of 4 or 8 bytes. That means that the last 2–3 bits of a pointer will always be 0 and will never be used. V8 will make use of that and will encode some type information inside the last bit. That would work like this:</p><p><strong>For pointers:</strong></p><pre>xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx<strong>1</strong></pre><p>For pointers, V8 will always set the last bit to 1. If that bit is 1, it means we are dealing with a pointer. That also means that before using that pointer, we need to clear that last bit (set it to 0) because it was set to 1 just to mark that variable as a pointer.</p><p><strong>For small integers (SMI):</strong></p><pre>xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx<strong>0</strong></pre><p>For small integers (SMI), the last bit will be set to 0. That means that small integers are 31bit long on 32 bit systems.</p><p>On 64bit systems it works slightly different - a SMI will be 32 bits and the lower 32 bits will always be set to 0:</p><pre>xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx<strong>00000000000000000000000000000000</strong></pre><p>But the principle is the same: if the last bit of a memory location is a 1, we are dealing with a pointer, and if it’s 0, we are dealing with a SMI.</p><p>Let’s try that out by creating the following array and doing a Debug Print on it in D8:</p><pre>a=[5,&quot;test&quot;]</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/957/1*OvjOQCbVJZFXUGKi8hBniQ.png" /></figure><p>Notice how all pointers in the debug output here have the last bit set to 1. If we want to use some of these pointers, we would have to clear the last bit of it, i.e. the address of elements of this array will become 02ae456d6e98 (instead of 02ae456d6e99). Let’s go to that address in WinDbg and inspect the elements:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*tT55y4q4USjdNhkywpQsfw.png" /></figure><p>There we’ll find our SMI 5 and right below it the pointer to our string “test”. The SMI is encoded exactly how we explained earlier. If we take in mind that memory is little-endian, our SMI looks like this in hex:</p><pre>00 00 00 05 00 00 00 00</pre><p>That means, lower 32 bits are set to 0, and higher 32 bits are used as the SMI value.</p><p>Perfect! :) Let’s now try to add an integer larger than 32 bits and a float to the array to see what will happen:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/957/1*cN0OrwsoIpUyvoLWrjH43g.png" /></figure><p>We see that both numbers have been stored on the heap. If we follow one of these pointers, we will see two things: 1) a pointer to a map (more on maps later), and the value of the number/float in <a href="https://en.wikipedia.org/wiki/IEEE_754">IEEE 754</a> encoded form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*vgHAXU_CNLte0QS00o1cbQ.png" /></figure><p>You can convert those values back to decimal form by using any IEEE 754 converter (64 bit in my case).</p><h4>Strings and other primitive types</h4><p>Similar to floats, strings will be stored in a similar way: a pointer pointing to a memory location containing two things: 1) a map describing the variable and 2) the value of the variable itself. Some primitives like null or undefined that do not contain any value will only be represented as a pointer to a map.</p><p>It is worth mentioning that although we talked about some types like strings and numbers as primitive types, it’s also possible to create them as objects:</p><pre>var a = &quot;test&quot;; //primitive type<br>var o = new String(&quot;test&quot;); //object</pre><p>So let’s talk about objects now.</p><h4>Objects</h4><p>Let’s create an object and do a Debug Print for it:</p><pre>var o={color:&quot;yellow&quot;,shape:&quot;round&quot;};</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/957/1*lDmcz0IqOrYNKpFqgGrcfw.png" /></figure><p>There are quite a few new things here, but let’s try to load the memory address of that object in WinDbg because the only goal for now is to understand how it’s laid out in memory:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*d3qbQsb3WZzidbH2kPs41Q.png" /></figure><p>To make sense of this, let’s first understand how a JS object is supposed to look like in memory:</p><pre>++++++++++++++++++++++++<br>+      JS OBJECT       +<br>++++++++++++++++++++++++<br>|         Map          |<br>------------------------<br>|      Properties      |<br>------------------------<br>|       Elements       |<br>------------------------<br>| In-Object Property 1 |<br>------------------------<br>| In-Object Property 2 |<br>------------------------<br>|         ...          |<br>------------------------</pre><p>That means, the first pointer at the memory location of the object is a pointer to the Map of that object. A Map is like hidden class that describes the layout of the object, mapping of property names to offsets, and few other things, like the pointer to the prototype of the object. Maps would be a topic on it’s own and I haven’t dug into that yet, but the memory layout of a Map itself and some other details can be found in the V8 source code: <a href="https://github.com/v8/v8/blob/master/src/objects/map.h">https://github.com/v8/v8/blob/master/src/objects/map.h</a></p><p>The second pointer is a pointer to the properties of that object. There are three types of object properties in V8:</p><ol><li>Very fast properites</li><li>Fast properties</li><li>Slow properties</li></ol><p>In case an object has just a few properties, V8 will just place them inside the object itself directly (In-Object properties in the Object graph above), and those would be very fast properties. In case there are too many properties, V8 will use that second pointer in the Object to point to an array that contains the other properties, which could in that case be Fast or Slow. I won’t dig into the details now, but more details can be found here: <a href="https://v8.dev/blog/fast-properties">https://v8.dev/blog/fast-properties</a></p><p>The third pointer in the Object is a pointer to the elements of the object. Elements are like properties but that have numeric names, i.e. {1:”green”, 2:”red&quot;}, which would be used in arrays.</p><p>After that pointer come all the very fast properties, and if you compare the 4th memory location/line in the memory layout in WinDbg from the screenshot above, you will see that it contains the address/pointer to the string/value of our first property.</p><p>So far so good. Off to figuring out what to explore next :)</p><h4>Resources</h4><p><a href="https://github.com/thlorenz/v8-perf/blob/master/data-types.md">https://github.com/thlorenz/v8-perf/blob/master/data-types.md</a></p><p><a href="https://stackoverflow.com/questions/7413168/how-does-v8-manage-the-memory-of-object-instances">https://stackoverflow.com/questions/7413168/how-does-v8-manage-the-memory-of-object-instances</a></p><p><a href="https://v8.dev/blog/fast-properties">https://v8.dev/blog/fast-properties</a></p><p><a href="https://javascript.info/primitives-methods">https://javascript.info/primitives-methods</a></p><p><a href="https://www.youtube.com/watch?v=5nmpokoRaZI">https://www.youtube.com/watch?v=5nmpokoRaZI</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ea37571276b8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[V8 Bug Hunting Part 1: Setting up the debug environment]]></title>
            <link>https://medium.com/@stankoja/v8-bug-hunting-part-1-setting-up-the-debug-environment-7ef34dc6f2de?source=rss-90b6c24d5272------2</link>
            <guid isPermaLink="false">https://medium.com/p/7ef34dc6f2de</guid>
            <category><![CDATA[v8]]></category>
            <category><![CDATA[bug-bounty]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Stanko Jankovic]]></dc:creator>
            <pubDate>Tue, 04 Jun 2019 19:31:19 GMT</pubDate>
            <atom:updated>2019-06-09T19:38:47.596Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Disclaimer: This is not really a write-up, but it’s just me taking notes. The content may chaotic, wrong or there may be better ways to do things. If you notice that, please point it out.</em></p><h4>Intro</h4><p>So far I was looking for bugs mostly in web apps, but the more I did it, the more I felt I was just scratching the surface. I want to dig deeper through the layers of abstraction and get down to the binary stuff.</p><p>Binary exploitation is a huge topic, and after looking/reading around for some time, I decided I need to focus on something. To get to the point, I picked Web Browsers, or more precisely, Javascript engines. Around the same time, LiveOverflow started posting great videos about that topic:</p><p><a href="https://www.youtube.com/watch?v=5tEdSoZ3mmE&amp;t=16s">https://www.youtube.com/watch?v=5tEdSoZ3mmE</a> (part 0x00)</p><p><a href="https://www.youtube.com/watch?v=yJewXMwj38s">https://www.youtube.com/watch?v=yJewXMwj38s</a> (part 0x01)</p><p>My goal is to follow along, but not with a focus on JavaScriptCore, but on the V8 engine, and I will use Windows/WinDbg instead of Mac/lldb.</p><h4>Compiling V8</h4><p>The first step would be to get a running V8 install on our machine. The following links will help:</p><p><a href="https://blog.angularindepth.com/how-to-build-v8-on-windows-and-not-go-mad-6347c69aacd4">https://blog.angularindepth.com/how-to-build-v8-on-windows-and-not-go-mad-6347c69aacd4</a></p><p><a href="http://www.lfdm.net/development/5-how-to-compile-v8-on-windows.html">http://www.lfdm.net/development/5-how-to-compile-v8-on-windows.html</a></p><p>It’s not a completely straightforward process and don’t worry if it takes you some time. Both tutorials are compiling it with is_debug=false, but you should set that to true because we want a debug build.</p><p>Note: As pointed out by <a href="https://twitter.com/geluchat?lang=en">Geluchat</a>, a debug build has also disadvantages: slow and bugs that would trigger on a release build may sometimes not trigger on a debug build. Using use_jumbo_build=true and is_compoment_build=false will speed up the build process.</p><p>At one moment I was stuck on the last compilation command with “ninja” which was returning “Permission denied” errors (even when run as admin). Rebuilding V8 in C:\V8 instead of in My Documents resolved the issue (not sure why). Simply moving the build from one folder to another would be a bad idea because it would mess up your debug symbols and source paths.</p><p>For now, I have compiled the latest version, but it will be useful to learn to compile older versions for analyzing past bugs too at some point.</p><h4>Running V8</h4><p>The V8 shell/debugger is called D8. It will be located here:</p><pre>[path_to_v8_folder]\out.gn\[build_name]\d8.exe</pre><p>You should run it with the --allow-natives-syntax flag in order to get access to the native functions like DebugPrint (which is similar to the “describe” function LiveOverflow is using in his videos):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7eAE5_YFJiNecPd5cuvj_A.png" /></figure><p>The memory layout of objects and the internal concepts are different in V8 compared to JavaScript Core. The concepts like Butterfly or Structure ID that LiveOverflow is describing in his videos and which are also described <a href="http://www.phrack.org/papers/attacking_javascript_engines.html">here</a> are JavaScript Core concepts and are not the samein V8 (I believe so). The garbage collector of V8 appears to work differently too.</p><p>Internal types also appear to be called differently (i.e. array with integers only is PACKED_SMI_ELEMENTS while an array with integers and doubles is a PACKED_DOUBLE_ELEMENTS - and the array will become HOLEY instead of PACKED if there is an empty space in it):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2Bq5MbbJ1QKLvMWcpFep5g.png" /></figure><p>DebugPrint is not the only internal function, and there are many more to explore:</p><p><a href="https://cs.chromium.org/chromium/src/v8/src/runtime/runtime.h?rcl=05720af2b09a18be5c41bbf224a58f3f0618f6be&amp;l=574">https://cs.chromium.org/chromium/src/v8/src/runtime/runtime.h?rcl=05720af2b09a18be5c41bbf224a58f3f0618f6be&amp;l=574</a></p><h4>Debugging V8</h4><p>LiveOverflow used lldb as the debugger. I’m gonna try to use WinDbg (no idea if that makes sense at all).</p><p>The first steps are relatively straightforward. You can either run D8 and attach to that process from WinDbg, or you can run the D8 executable from WinDbg directly. Once done, you can hit F5 to continue running the program. After that, you can start experimenting.</p><p>Lets try to create an array with couple of strings and do a DebugPrint on it:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eBXfW_1VAS9WYllvKHek-g.png" /></figure><p>Under “elements”, we see the address where the elements of the array are stored - in this case, the elements are two pointers to strings (we see the values of the pointers too). We can try to look at the address of the array elements in WinDbg (memory window — we need to pause execution in order to be able to search for an address).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C_ccZ96QbyBcRhUtDQ_Wtg.png" /></figure><p>There we’ll see the pointer to the first string. Don’t forget that memory is little-endian. If we would go to that address, we would find the string:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gDqVgQ9o5kZ-K4rJpMbn-w.png" /></figure><p>If we repeat the same with an array of integers (well, in JS those are numbers, not integers), the array would not be made of pointers, but of the integers we defined:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6uXE-ehnLxkFcZzmT2HZeQ.png" /></figure><p>If we go to the “elements” address, we would see them:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*X9BbacHDCkkE8t3pRycjzw.png" /></figure><p>Interesting to observe, the integers in the examples LiveOverflow was demonstrating in his 0x01 video had some high bytes set to FFFF. That’s because JS Core is using NaN-boxing, and V8 does not. The way arrays are stored appears to be different to. There are no mentions of butterflies or structure IDs. It seems those are JS Core concepts. But we’ll still have to find out how V8 internals work.</p><p>One more thing to try before we wrap up Part 1: Can we set a breakpoint on Math.max like LiveOverflow did it and step through the source code of that function? First we need to find that function in order to set the breakpoint. We can search for symbols like this in WinDbg:</p><pre>X v8!*Mathmax*</pre><p>Result:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uGyJtuQlRLV4Y6sGK6fCoQ.png" /></figure><p>We can then set a breakpoint:</p><pre>bp v8!Builtins_MathMax</pre><p>We then run Math.max in D8 and the breakpoint is hit:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lE3-jXEfcrqrEqor5a1mrw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*P96rDOcbLH1YRZ9X0HR-Vg.png" /></figure><p>But I don’t see any source code? If I open the call stack window, I can see that the source code is available for most of the function in the call stack, but not for the v8!Builtins_* functions that are on top of the stack. But why?</p><p>After googling for a bit, I came across this:</p><p><a href="https://v8.dev/docs/csa-builtins">https://v8.dev/docs/csa-builtins</a></p><p>It turns out that many builtin function are not done in C++, but are either hardcoded in assembly or implemented using the CodeStubAssembler infrastructure. But some are still written in C++. By browsing the source code a bit, I found that Math.hypot should be one of such functions. So I tried setting a breakpoint on bp v8!Builtins_MathHypot. I run everything again, hit the breakpoint, but still the same result. No source code. WHY???!!!</p><p>I asked on StackOverflow:</p><p><a href="https://stackoverflow.com/questions/56443262/how-to-debug-v8-with-source-code-view-using-windbg">https://stackoverflow.com/questions/56443262/how-to-debug-v8-with-source-code-view-using-windbg</a></p><p>I did not expect to get an answer, but I did. As suggested, I have set the breakpoint directly in the source code, and when I hit it, i was able to step through the source code! I also noticed that my mistake previousy was that I was setting a breakpoint on v8!Builtin_MathHypot instead of v8!v8::internal::Builtin_MathHypot.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*S__DqNF6IINLEYJC1hPBtA.png" /></figure><p>Ok, I’m happy with the progress so far. Now I’m gonna watch the 0x02 video of LiveOverflow and figure out what to explore next :)</p><p><a href="https://medium.com/@stankoja/v8-bug-hunting-part-2-memory-representation-of-js-types-ea37571276b8">V8 Bug Hunting Part 2: Memory representation of JS types</a> &gt;&gt;&gt;</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7ef34dc6f2de" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Exploit Exercises Nebula Level 18 : Another way to solve it]]></title>
            <link>https://medium.com/@stankoja/exploit-exercises-nebula-level-18-another-way-to-solve-it-9ec64052a0f1?source=rss-90b6c24d5272------2</link>
            <guid isPermaLink="false">https://medium.com/p/9ec64052a0f1</guid>
            <category><![CDATA[linux]]></category>
            <category><![CDATA[exploit-exercise]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[security]]></category>
            <dc:creator><![CDATA[Stanko Jankovic]]></dc:creator>
            <pubDate>Fri, 28 Jul 2017 13:14:16 GMT</pubDate>
            <atom:updated>2017-07-28T13:14:16.852Z</atom:updated>
            <content:encoded><![CDATA[<p>I had some fun with solving Nebula <a href="https://exploit-exercises.com/nebula/level18/">level 18</a> at <a href="http://exploit-exercises.com/">exploit-exercises.com</a> and after finding several ways to solve it, I looked up some blog posts to see other peoples approaches, and noticed that one of my solutions is different than the solutions of most other people, so I thought I should share it :)</p><p>I don’t want to spoil anything, so if you haven’t tried to solve <a href="https://exploit-exercises.com/nebula/level18/">level 18</a> yet, you can give it a try first before you go ahead and read the rest of this blog post.</p><p>The first solution I found was the solution that most blog posts about this level describe: simply max out the file descriptor count to prevent the program from reading the password file, and it will log you in. I will not talk about this solution because it has already been described in detail by many blogs. Just <a href="https://www.google.com/search?q=nebula+level+18+solution">google it up</a>.</p><p>There are also two memory corruption bugs (one buffer overflow and one format string bug) which were easy to spot, but hard to exploit because the OS has ASLR activated, and the binary has been compiled with buffer overflow protection flags. I did not even try to exploit these (but will one day).</p><p>But one thing that was bugging me was the fact that the user is able to specify the name of the debug file of the binary. That means that I can basically set the password file as the debug file, and write to it. Could I just write some password to the password file and use it to log in?</p><p>That is not easy because we are very limited in what we can write to the password file. When the program starts, it will automatically write the following string to the debug/password file (where %d is the debug level that you control by specifying -v arguments):</p><pre>&quot;Starting up. Verbose level = %d\n&quot;</pre><p>But we can’t use this string as the password because of the newline character. If you look at the source code of the program, it will replace the first occurrence of a newline character with a null byte, which is just one reason that would make it impossible to enter a newline character as part of your password.</p><p>But can we somehow remove the newline character from the password file? The answer is yes: by writing to the passwords file from two instances of the vulnerable binary. This is how it can be done:</p><ol><li>First just run the binary with the following parameters:</li></ol><pre> /home/flag18/flag18 -d password -v</pre><p>This will start the binary in debug level 1 and write the following string to the password file:</p><pre>&quot;Starting up. Verbose level = 1\n&quot;</pre><p>It is important to note that it will start to write from the first position of the file, and will “remember” how many chars it has written so that if it has to write another string, it can just append it to the already written data.</p><p>2. Now suspend the running program with CTRL+Z, and run a new instance by using the following parameters:</p><pre>/home/flag18/flag18 -d password -vvvvvvvvvv</pre><p>This will start the binary in debug level 10 and write the following string to the password file:</p><pre>&quot;Starting up. Verbose level = 10\n&quot;</pre><p>Since this is a different process and a different file descriptor, it will simply start writing form the first position of the file and overwrite the existing string that the first instance has written. Notice that this string is by one char longer than the string that the first instance wrote (debug level 1 vs debug level 10).</p><p>3. What will happen if we suspend the second instance with CTRL+Z, and bring the first instance back with “fg 1”, and make it write something to the debug/password file? It will simply continue to write to the file at the position after the last character of the first string. But because we have changed the string using the second instance of the program, that means that the first instance would now overwrite the newline character!</p><p>We just have to find a way to now print a string without a newline character in it (otherwise we would just come back to the initial problem), and that is easily possible with the following command (from inside the first instance of the program):</p><pre>site exec tttttttttttttttttttttttttttttt</pre><p>I just added many padding letters in order to be sure to overwrite the newline character of the string the second instance wrote. Now, the content of the password file is:</p><pre>Starting up. Verbose level = 10tttttttttttttttttttttttttttttt</pre><p>Now we can simply close both instances, run a new one without any parameters, and use that whole string as the password, because it does not contain a newline character anymore :)</p><p>For infosec related stuff, please follow me at Twitter: <a href="https://twitter.com/stankoja">https://twitter.com/stankoja</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9ec64052a0f1" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>