Publications‎ > ‎

International Conference Publications

On the Automatic Design of a Representation for Grammar-based Genetic Programming

posted Dec 27, 2017, 3:31 AM by Eric Medvet   [ updated Mar 7, 2018, 8:48 AM ]

  • 21st European Conference on Genetic Programming (EuroGP), 2018, Parma (Italy)
  • Eric Medvet, Alberto Bartoli
A long-standing problem in Evolutionary Computation consists in how to choose an appropriate representation for the solutions. In this work we investigate the feasibility of synthesizing a representation automatically, for the large class of problems whose solution spaces can be defined by a context-free grammar. We propose a framework based on a form of meta-evolution in which individuals are candidate representations expressed with an ad hoc language that we have developed to this purpose. Individuals compete and evolve according to an evolutionary search aimed at optimizing such representation properties as redundancy, locality, uniformity of redundancy.
We assessed experimentally three variants of our framework on established benchmark problems and compared the resulting representations to human-designed representations commonly used (e.g., classical Grammatical Evolution). The results are promising in the sense that the evolved representations indeed exhibit better properties than the human-designed ones. Furthermore, while those improved properties do not result in a systematic improvement of search effectiveness, some of the evolved representations do improve search effectiveness over the human-designed baseline.

Impact of Code Obfuscation on Android Malware Detection based on Static and Dynamic Analysis

posted Nov 22, 2017, 8:43 AM by Eric Medvet   [ updated Feb 9, 2018, 6:21 AM ]

The huge diffusion of malware in mobile platform is plaguing users. New malware proliferates at a very fast pace: as a matter of fact, to evade the signature-based mechanism implemented in current antimalware, the application of trivial obfuscation techniques to existing malware is sufficient. In this paper, we show how the application of several morphing techniques affects the effectiveness of two widespread malware detection approaches based on Machine Learning coupled respectively with static and dynamic analysis. We demonstrate experimentally that dynamic analysis-based detection performs equally well in evaluating obfuscated and non-obfuscated malware. On the other hand, static analysis-based detection is more accurate on non-obfuscated samples but is greatly negatively affected by obfuscation: however, we also show that this effect can be mitigated by using obfuscated samples also in the learning phase.

VizMal: A Visualization Tool for Analyzing the Behavior of Android Malware

posted Nov 22, 2017, 8:38 AM by Eric Medvet   [ updated Nov 22, 2017, 8:38 AM ]

  • International Workshop on FORmal methods for Security Engineering (ForSE), 2018, Madeira (Portugal), to appear
  • Alessandro Bacci, Fabio Martinelli, Eric Medvet, Francesco Mercaldo
Malware signature extraction is currently a manual and a time-consuming process. As a matter of fact, security analysts have to manually inspect samples under analysis in order to find the malicious behavior. From research side, current literature is lacking of methods focused on the malicious behavior localization: designed approaches basically mark an entire application as malware or non-malware (i.e., take a binary decision) without knowledge about the malicious behavior localization inside the analysed sample. In this paper, with the twofold aim of assisting the malware analyst in the inspection process and of pushing the research community in malicious behavior localization, we propose VizMal, a tool for visualizing the dynamic trace of an Android application which highlights the portions of the application which look potentially malicious. VizMal performs a detailed analysis of the application activities showing for each second of the execution whether the behavior exhibited is legitimate or malicious. The analyst may hence visualize at a glance when at to which degree an application execution looks malicious.

A Language for UAV Traffic Rules in an Urban Environment and Decentralized Scenario

posted Sep 1, 2017, 4:02 AM by Eric Medvet   [ updated Oct 13, 2017, 5:48 AM ]

  • IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2017, Boston (Massachusetts, US), to appear
  • Giuseppe Lombardi, Eric Medvet, Alberto Bartoli
Unmanned Aerial Vehicles (UAVs) are becoming increasingly popular and the amount of UAV traffic in urban environments will largely increase in the future, due to profitable tasks which are particularly suited to UAVs, e.g., parcel delivery and surveillance, in particular in the context of smart cities. Trying to ensure the traffic safety and efficiency by acting on the UAV controller alone might be challenging, since the set of involved players (regulators, manufacturers, business users) is large and diversified. In this work, we address this problem by proposing a language for defining rules suitable for UAV traffic which can be enforced in a decentralized way by the UAVs themselves, without any need for communication and regardless of the UAV navigation algorithm. The language allows to express realistic rules, such as "when cruising, keep a minimum altitude", concisely and such that they can be processed online by each single UAV basing on its perception of the nearby environment. We experimentally validate the ability of our proposal to impact on the UAV traffic efficiency and safety by performing a large number of simulations with and without a set of realistic rules.

The DU Map: A Visualization to Gain Insights into Genotype-Phenotype Mapping and Diversity

posted Apr 20, 2017, 5:52 AM by Eric Medvet   [ updated Jul 21, 2017, 5:11 AM ]

The relation between diversity and genotype to phenotype mapping has been the focus of several studies. In those Evolutionary Algorithms (EAs) where the genotype is a sequence of symbols, the contribution of each of those symbols in determining the phenotype may vary greatly, possibly being null. In the latter case, the unused portions of the genotype may host a large amount of the population diversity. However, reasoning on coarse-grained measures makes it hard to validate such a claim and, more in general, to gain insights into the interactions between genotype-phenotype mapping and diversity. In this paper, we propose a novel visualization which summarizes in a single, compact heat map (the DU map), three kinds of information: (a) how diverse are the genotypes in the population at the level of single symbols; (b) if and to what degree each individual symbol in the genotype contributes to the phenotype; (c) how the two previous measures vary during the evolution. We experimentally verify the usefulness of the DU map w.r.t. its primary goal and, more broadly, when used to analyze different EA design options. We apply it to Grammatical Evolution (GE) as it constitutes an ideal testbed for the DU map, due to the availability of different mapping functions.

Evolvability in Grammatical Evolution

posted Mar 22, 2017, 3:30 AM by Eric Medvet   [ updated Jul 7, 2017, 9:11 AM ]

Evolvability is a measure of the ability of an Evolutionary Algorithm (EA) to improve the fitness of an individual when applying a genetic operator. Other than the specific problem, many aspects of the EA may impact on the evolvability, most notably the genetic operators and, if present, the genotype-phenotype mapping function. Grammatical Evolution (GE) is an EA in which the mapping function plays a crucial role since it allows to map any binary genotype into a program expressed in any user-provided language, defined by a context-free grammar. While GE mapping favored a successful application of GE to many different problems, it has also been criticized for scarcely adhering to the variational inheritance principle, which itself may hamper GE evolvability. In this paper, we experimentally study GE evolvability in different conditions, that is, problems, mapping functions, genotype sizes, and genetic operators. Results suggest that there is not a single factor determining GE evolvability: in particular, the mapping function alone does not deliver better evolvability regardless of the problem. Instead, GE redundancy, which itself is the result of the combined effect of several factors, has a strong impact on the evolvability.

Hierarchical Grammatical Evolution

posted Mar 22, 2017, 3:28 AM by Eric Medvet   [ updated Jul 21, 2017, 5:15 AM ]

We present Hierarchical Grammatical Evolution (HGE) and its variant WHGE, two novel genotype-phenotype mapping procedures to be used in the Grammatical Evolution (GE) framework. HGE/WHGE are designed to exhibit better variational inheritance than standard GE without imposing any constraint on the structure of the genotype nor on the genetic operators. Our proposal considers the phenotype as a hierarchy of non-terminal expansions and is based on two key ideas: (i) the closer the non-terminal to be expanded to the root of the hierarchy, the larger the genotype substring determining its expansion, and
(ii) upon expansion, a non-terminal divides its genotype substring among the resulting non-terminals. We experimentally evaluate our proposals on a set of benchmark problems and show that for the majority of them WHGE outperforms GE (and its variant piGE).

An Effective Diversity Promotion Mechanism in Grammatical Evolution

posted Mar 22, 2017, 3:23 AM by Eric Medvet   [ updated Jul 21, 2017, 5:16 AM ]

Grammatical Evolution is an Evolutionary Algorithm which can evolve programs in any language described by a context-free grammar. A sequence of bits (the genotype) is transformed into a string of the language (the phenotype) by means of a mapping function, and eventually into a fitness value. Unfortunately, the flexibility brought by the mapping is also likely to introduce non-locality phenomena, reduce diversity, and consequently hamper the effectiveness of the algorithm. In this paper, we propose a novel technique for promoting diversity, able to  operate on three different levels: genotype, phenotype, and fitness. The technique is quite general, independent both from the specific problem being tackled and from other components of the evolutionary algorithm, such as genotype-phenotype mapping, selection criteria, and genetic operators. We experimentally demonstrate its efficacy in a wide range of conditions and from different points of view. The results also confirm the preponderant importance of the phenotype-level analyses in diversity promotion.

Road Traffic Rules Synthesis using Grammatical Evolution

posted Jan 11, 2017, 1:59 PM by Eric Medvet   [ updated Apr 6, 2017, 3:12 AM ]

We consider the problem of the automatic synthesis of road traffic rules, motivated by a future scenario in which human and machine-based drivers will coexist on the roads: in that scenario, current road rules may be either unsuitable or inefficient. We approach the problem using Grammatical Evolution (GE). To this end, we propose a road traffic model which includes concepts amenable to be regulated (e.g., lanes, intersections) and which allows drivers to temporarily evade traffic rules when there are no better alternatives. In our GE framework, each individual is a set of rules and its fitness is a weighted sum of traffic efficiency and safety, as resulting from a number of simulations where all drivers are subjected to the same rules. Experimental results show that our approach indeed generates rules leading to a safer and more efficient traffic than enforcing no rules or rules similar to those currently used.

A Comparative Analysis of Dynamic Locality and Redundancy in Grammatical Evolution

posted Jan 11, 2017, 1:55 PM by Eric Medvet   [ updated Mar 22, 2017, 3:17 AM ]

Grammatical Evolution (GE) is an Evolutionary Algorithm which can address any problem whose solution space may be described in terms of a context-free grammar: its most salient feature is a procedure which maps genotypes to phenotypes using the grammar production rules. The search effectiveness of GE may be affected by low locality and high redundancy, which can prevent GE to comply with the basic principle that offspring should inherit some traits from their parents. Indeed, many studies previously investigated the locality and redundancy of GE as originally proposed in [Ryan et al., 1998]. In this paper, we extend those results by considering redundancy and locality during the evolution, rather than statically, hence trying to understand if and how they are influenced by the selective pressure determined by the fitness. Moreover, we consider not only the original GE formulation, but three other variants proposed later. We experimentally find that there is an interaction between locality/redundancy and other evolution-related measures, namely diversity and growth of individual size.

1-10 of 61