Spelling suggestions: "subject:"eontrol flow graph"" "subject:"7control flow graph""
1 |
Construction of GCCFG for Inter-procedural Optimizations in Software Managed Manycore (SMM)January 2014 (has links)
abstract: Software Managed Manycore (SMM) architectures - in which each core has only a scratch pad memory (instead of caches), - are a promising solution for scaling memory hierarchy to hundreds of cores. However, in these architectures, the code and data of the tasks mapped to the cores must be explicitly managed in the software by the compiler. State-of-the-art compiler techniques for SMM architectures require inter-procedural information and analysis. A call graph of the program does not have enough information, and Global CFG, i.e., combining all the control flow graphs of the program has too much information, and becomes too big. As a result, most new techniques have informally defined and used GCCFG (Global Call Control Flow Graph) - a whole program representation which captures the control-flow as well as function call information in a succinct way - to perform inter-procedural analysis. However, how to construct it has not been shown yet. We find that for several simple call and control flow graphs, constructing GCCFG is relatively straightforward, but there are several cases in common applications where unique graph transformation is needed in order to formally and correctly construct the GCCFG. This paper fills this gap, and develops graph transformations to allow the construction of GCCFG in (almost) all cases. Our experiments show that by using succinct representation (GCCFG) rather than elaborate representation (GlobalCFG), the compilation time of state-of-the-art code management technique [4] can be improved by an average of 5X, and that of stack management [20] can be improved by an average of 4X. / Dissertation/Thesis / Masters Thesis Computer Science 2014
|
2 |
Software Architecture-Based Failure PredictionMohamed, ATEF 28 September 2012 (has links)
Depending on the role of software in everyday life, the cost of a software failure can sometimes be unaffordable. During system execution, errors may occur in system components and failures may be manifested due to these errors. These errors differ with respect to their effects on system behavior and consequent failure manifestation manners. Predicting failures before their manifestation is important to assure system resilience. It helps avoid the cost of failures and enables systems to perform corrective actions prior to failure occurrences. However, effective runtime error detection and failure prediction techniques encounter a prohibitive challenge with respect to the control flow representation of large software systems with intricate control flow structures. In this thesis, we provide a technique for failure prediction from runtime errors of large software systems. Aiming to avoid the possible difficulties and inaccuracies of the existing Control Flow Graph (CFG) structures, we first propose a Connection Dependence Graph (CDG) for control flow representation of large software systems. We describe the CDG structure and explain how to derive it from program source code. Second, we utilize the proposed CDG to provide a connection-based signature approach for control flow error detection. We describe the monitor structure and present the error checking algorithm. Finally, we utilize the detected errors and erroneous state parameters to predict failure occurrences and modes during system runtime. We craft runtime signatures based on these errors and state parameters. Using system error and failure history, we determine a predictive function (an estimator) for each failure mode based on these signatures. Our experimental evaluation for these techniques uses a large open-source software (PostgreSQL 8.4.4 database system). The results show highly efficient control flow representation, error detection, and failure prediction techniques. This work contributes to software reliability by providing a simple and accurate control flow representation and utilizing it to detect runtime errors and predict failure occurrences and modes with high accuracy. / Thesis (Ph.D, Computing) -- Queen's University, 2012-09-25 23:44:12.356
|
3 |
Désassemblage et détection de logiciels malveillants auto-modifiants / Disassembly and detection of self-modifying malwaresThierry, Aurélien 11 March 2015 (has links)
Cette thèse porte en premier lieu sur l'analyse et le désassemblage de programmes malveillants utilisant certaines techniques d'obscurcissement telles que l'auto-modification et le chevauchement de code. Les programmes malveillants trouvés dans la pratique utilisent massivement l'auto-modification pour cacher leur code utile à un analyste. Nous proposons une technique d'analyse hybride qui utilise une trace d'exécution déterminée par analyse dynamique. Cette analyse découpe le programme auto-modifiant en plusieurs sous-parties non auto-modifiantes que nous pouvons alors étudier par analyse statique en utilisant la trace comme guide. Cette seconde analyse contourne d'autres techniques de protection comme le chevauchement de code afin de reconstruire le graphe de flot de contrôle du binaire analysé. Nous étudions également un détecteur de programmes malveillants, fonctionnant par analyse morphologique : il compare les graphes de flot de contrôle d'un programme à analyser à ceux de programmes connus comme malveillants. Nous proposons une formalisation de ce problème de comparaison de graphes, des algorithmes permettant de le résoudre efficacement et détaillons des cas concrets d'application à la détection de similarités logicielles / This dissertation explores tactics for analysis and disassembly of malwares using some obfuscation techniques such as self-modification and code overlapping. Most malwares found in the wild use self-modification in order to hide their payload from an analyst. We propose an hybrid analysis which uses an execution trace derived from a dynamic analysis. This analysis cuts the self-modifying binary into several non self-modifying parts that we can examine through a static analysis using the trace as a guide. This second analysis circumvents more protection techniques such as code overlapping in order to recover the control flow graph of the studied binary. Moreover we review a morphological malware detector which compares the control flow graph of the studied binary against those of known malwares. We provide a formalization of this graph comparison problem along with efficient algorithms that solve it and a use case in the software similarity field
|
4 |
The Efficacy of Forward-Edge Control-Flow Integrity in Mitigating Memory Corruption Vulnerabilities : The Case of the Android StackOlofsson, Viktor January 2023 (has links)
Memory corruption is one of the oldest and most prominent problems in the field of computer security. In order to protect the vulnerabilities that arise from memory corruption, a mitigation technique called Control-flow Integrity (CFI) was developed. The Android Open Source Project utilizes a specific implementation of the CFI policy called forward-edge CFI in the compilation of the Android system. However, memory corruption vulnerabilities are still a problem for Android systems. This raises the question: Is forward-edge CFI really effective in mitigating memory corruption vulnerabilities? In this research, the efficacy of forward-edge CFI in terms of mitigating memory corruption vulnerabilities in Android systems is analyzed. This is done by analyzing nine Common Vulnerabilities and Exposures (CVE) in terms of how they can be exploited and whether forward-edge CFI could mitigate them. Additionally, the Android binaries containing the vulnerabilities are analyzed in an attempt to detect the presence of CFI instrumentation. CFI was detected in one of nine vulnerable Android binaries, implying that there exist memory corruption vulnerabilities that forward-edge CFI definitely can not protect. The analysis of nine CVEs showed that five CVEs could be mitigated by forward-edge CFI. These results indicate that forward-edge CFI could definitely mitigate a portion of the memory corruption vulnerabilities plaguing Android systems. However, in order to protect a greater portion of memory corruption vulnerabilities, forward-edge CFI should be combined with other mitigation techniques such as Shadow Stacks.
|
5 |
Highlight and execute suspicious paths in Android malware / Mettre en avant et exécuter les chemins suspicieux dans les malwares AndroidLeslous, Mourad 18 December 2018 (has links)
Les smartphones sont devenus omniprésents dans notre vie quotidienne à cause des options qu'ils proposent. Aujourd'hui, Android est installé sur plus de 80% des smartphones. Les applications mobiles recueillent une grande quantité d'informations sur l'utilisateur. Par conséquent, Android est devenu une cible préférée des cybercriminels. Comprendre le fonctionnement des malwares et comment les détecter est devenu un défi de recherche important. Les malwares Android tentent souvent d'échapper à l'analyse statique en utilisant des techniques telles que l'obfuscation et le chargement dynamique du code. Des approches d'analyse ont été proposées pour exécuter l'application et surveiller son comportement. Néanmoins, les développeurs des malwares utilisent des bombes temporelles et logiques pour empêcher le code malveillant d'être exécuté sauf dans certaines circonstances. Par conséquent, plus d'actions sont requises pour déclencher et surveiller leurs comportements. Des approches récentes tentent de caractériser automatiquement le comportement malveillant en identifiant les endroits du code les plus suspicieux et en forçant leur exécution. Elles se basent sur le calcul des graphes de flot de contrôle (CFG) qui sont incomplets, car ils ne prennent pas en considération tous les types de chemins d'exécution. Ces approches analysent seulement le code d'application et ratent les chemins d'exécution générés quand l'application appelle une méthode du framework, qui appelle à son tour une autre méthode applicative. Nous proposons GPFinder, un outil qui extrait automatiquement les chemins d'exécution qui mènent vers les endroits suspicieux du code, en calculant des CFG qui incluent les appels interprocéduraux explicites et implicites. Il fournit aussi des informations clés sur l'application analysée afin de comprendre comment le code suspicieux a été injecté dans l'application. Pour valider notre approche, nous utilisons GPFinder pour étudier une collection de 14224 malwares Android. Nous évaluons que 72,69% des échantillons ont au moins un endroit suspicieux du code qui n'est atteignable qu'à travers des appels implicites. Les approches de déclenchement actuelles utilisent principalement deux stratégies pour exécuter une partie du code applicatif. La première stratégie consiste à modifier l'application excessivement pour lancer le code ciblé sans faire attention à son contexte originel. La seconde stratégie consiste à générer des entrées pour forcer le flot de contrôle à prendre le chemin désiré sans modifier le code d'application. Cependant, il est parfois difficile de lancer un endroit spécifique du code seulement en manipulant les entrées. Par exemple, quand l'application fait un hachage des données fournies en entrée et compare le résultat avec une chaîne de caractères fixe pour décider quelle branche elle doit prendre. Clairement, le programme de manipulation d'entrée devrait inverser la fonction de hachage, ce qui est presque impossible. Nous proposons TriggerDroid, un outil qui a deux buts : forcer l'exécution du code suspicieux et garder le contexte originel de l'application. Il fournit les événements framework requis pour lancer le bon composant et satisfait les conditions nécessaires pour prendre le chemin d'exécution désiré. Pour valider notre approche, nous avons fait une expérience sur 135 malwares Android de 71 familles différentes. Les résultats montrent que notre approche nécessite plus de raffinement et d'adaptation pour traiter les cas spéciaux dus à la grande diversité des échantillons analysés. Finalement, nous fournissons un retour sur les expériences que nous avons conduites sur différentes collections, et nous expliquons notre processus expérimental. Nous présentons le dataset Kharon, une collection de malwares Android bien documentés qui peuvent être utilisés pour comprendre le panorama des malwares Android. / The last years have known an unprecedented growth in the use of mobile devices especially smartphones. They became omnipresent in our daily life because of the features they offer. They allow the user to install third-party apps to achieve numerous tasks. Smartphones are mostly governed by the Android operating system. It is today installed on more than 80% of the smartphones. Mobile apps collect a huge amount of data such as email addresses, contact list, geolocation, photos and bank account credentials. Consequently, Android has become a favorable target for cyber criminals. Thus, understanding the issue, i.e., how Android malware operates and how to detect it, became an important research challenge. Android malware frequently tries to bypass static analysis using multiple techniques such as code obfuscation and dynamic code loading. To overcome these limitations, many analysis techniques have been proposed to execute the app and monitor its behavior at runtime. Nevertheless, malware developers use time and logic bombs to prevent the malicious code from executing except under certain circumstances. Therefore, more actions are needed to trigger it and monitor its behavior. Recent approaches try to automatically characterize the malicious behavior by identifying the most suspicious locations in the code and forcing them to execute. They strongly rely on the computation of application global control flow graphs (CFGs). However, these CFGs are incomplete because they do not take into consideration all types of execution paths. These approaches solely analyze the application code and miss the execution paths that occur when the application calls a framework method that in turn calls another application method. We propose in this dissertation a tool, GPFinder, that automatically exhibits execution paths towards suspicious locations in the code by computing global CFGs that include edges representing explicit and implicit interprocedural calls. It also gives key information about the analyzed application in order to understand how the suspicious code was injected into the application. To validate our approach, we use GPFinder to study a collection of 14,224 malware samples, and we evaluate that 72.69% of the samples have at least one suspicious code location which is only reachable through implicit calls. Triggering approaches mainly use one of the following strategies to run a specific portion of the application's code: the first approach heavily modifies the app to launch the targeted code without keeping the original behavioral context. The second approach generates the input to force the execution flow to take the desired path without modifying the app's code. However, it is sometimes hard to launch a specific code location just by fuzzing the input. For instance, when the application performs a hash on the input data and compares the result to a fixed string to decide which branch of the condition to take, the fuzzing program should reverse the hashing function, which is obviously a hard problem. We propose in this dissertation a tool, TriggerDroid, that has a twofold goal: force the execution of the suspicious code and keep its context close to the original one. It crafts the required framework events to launch the right app component and satisfies the necessary triggering conditions to take the desired execution path. To validate our approach, we led an experiment on a dataset of 135 malware samples from 71 different families. Results show that our approach needs more refinement and adaptation to handle special cases due to the highly diverse malware dataset that we analyzed. Finally, we give a feedback on the experiments we led on different malware datasets, and we explain our experimental process. Finally, we present the Kharon dataset, a collection of well documented Android malware that can be used to understand the malware landscape.
|
6 |
Estimador e caracterizador de consumo de energia para software embarcadoSilva, Francisco Coelho da 24 March 2011 (has links)
Made available in DSpace on 2015-04-22T22:00:44Z (GMT). No. of bitstreams: 1
Francisco.pdf: 2605316 bytes, checksum: ee1fad3d9d9e7780947fc166b5909203 (MD5)
Previous issue date: 2011-03-24 / The energy consumption in the past years became a very important issue in embedded system projects. The high production and wide application of mobile devices have forced the emergence of various restrictions to this system, such as: weight, size and lifetime of batteries and multiple functionalities. Mobile devices works under limited power source that autonomy and lifetime are directly related to energy consumption of the running applications. These concerns have contributed significantly to include the energy consumption as metric for project quality in embedded systems.
The main goal of this work is to propose metrics, estimative and compare the energy consumption of programs code written in ANSI-C language, based on execution time of embedded systems. In order to support the approach it was improved a tool in algorithm level known as PESTI in multiple scenarios.
It was written a program in ANSI-C language and loaded in processor of the ARM 7 family s. Then, it was added into this program flags to signalize start and stop in order to measure execution time of each track in analysis.
The estimative tool already modified to attribute multiple scenarios, for a program written in ANSI-C and translated into an annotated control flow graph, with tracks assignments of probabilities. This model is probabilistically simulated by using Monte Carlo methodology. The proposed approach was validate carrying out a series of experimental in order to show the viability of the improved tool of estimation and characterization, which together will make the estimates of energy consumption somewhat more feasible.
Validate the proposed approach added;
Compare the results between simulation time and the tool for characterization PESTI with the same hardware platform embedded (ARM7).
The experimental were divided in three steps:
Simulation of the code in the tool PESTI in multiple scenarios;
Characterization of the query code;
Comparison of the characterization tool and PESTI.
The experiments were conducted on:
AMD Turion (tm) II Dual Core Mobile Processor M500, 2.20GHz, 4Gb of RAM;
OS Linux Mint Distribution kernel 2.6.22 32-bit;
11
OS Windows 7 32-bit. / Consumo de energia nos últimos anos tornou-se um aspecto importante em projetos de sistemas embarcados. A produção e utilização em larga escala dos dispositivos móveis tem imposto várias restrições como: peso, tamanho, tempo de vida útil da bateria e funcionalidades complexas. Dispositivos móveis operam sob uma fonte de energia limitada cuja autonomia e tempo de vida útil estão diretamente relacionados ao consumo de energia das aplicações. Estas questões contribuíram para incluir o consumo de energia como métrica de qualidade no projeto de sistemas embarcados.
Este trabalho tem como objetivo propor uma abordagem de medição, estimação e comparação do consumo de energia de código de programas escritos em linguagem ANSI-C, baseados em ensaios de códigos previamente escolhidos com características de consumo de energia e no tempo de execução. Para dar suporte à abordagem, uma ferramenta de estimação chamada PESTI foi estendida para atender múltiplos cenários probabilísticos.
Programas escritos em linguagem ANSI-C são embarcados no processador LPC2148 da família ARM 7. Nesse programa são inseridos flags de sinalização para start e stop, para delimitar o tempo de execução e medirmos o consumo de energia do código. Um hardware chamado de caracterizador de consumo de energia auxiliará na medição em tempo real de execução do código.
A ferramenta de estimação chamada PESTI com características probabilísticas e atribuições para múltiplos cenários probabilísticos é usada para estimar o consumo de energia do programa escrito em ANSI-C.
Validamos a abordagem proposta, executando um conjunto de experimentos mostrando a viabilidade da extensão da ferramenta de estimação e o caracterizador que, em conjunto, viabilizarão as estimativas de consumo de energia no processador alvo.
As atividades realizadas para a execução dos experimentos foram:
Validar a abordagem proposta;
Comparar os resultados medidos e estimados entre a ferramenta PESTI com o caracterizador para a mesma plataforma de hardware embarcada (ARM7).
Os experimentos foram divididos em três passos:
Estimação dos códigos na ferramenta PESTI em simples e múltiplos cenários;
Caracterização do código em questão;
Comparação da caracterização e ferramenta PESTI.
9
Onde os resultados obtidos mostram uma diferença entre os valores estimados e simulados e os resultados medidos.
Os experimentos foram conduzidos sobre:
AMD Turion(tm) II Dual Core Mobile M500, 2.20GHz, 4GB de RAM;
SO Linux Distribuição Mint kernel 2.6.22;
SO de 32 bits Windows 7.
|
7 |
Programmation Web Réactive dans un cadre typé statiquement pour l'orchestration de contenus multimédia riches / Reactive Web Programming in a Static Typing Context for Rich Multimedias Content OrchestrationEl Sibaïe Besognet, Rémy 12 July 2018 (has links)
Le but de cette thèse est d'apporter de nouvelles possibilités au domaine de la programmation Web, dont les technologies répandues ne capturent pas toutes les problématiques engendrées par les interactions dans une application. Notre solution est un langage, Pendulum, inspiré de la programmation synchrone réactive en Esterel et se présentant comme une extension à OCaml. Il permet de gagner en sûreté et en expressivité en particulier dans la gestion d'interaction multiples. Dans une première partie, nous présentons notre perception de la programmation Web d'aujourd'hui en partant du standard pour aller vers les technologies plus modernes qui tentent de subvenir aux besoins des programmes par d'autres approches, notamment la programmation multitier et les modèles de concurrence en flot de données. Dans une seconde partie, nous introduisons le langage Pendulum et ses constructions, ce qu'il propose comme interopérabilité avec le client Web le différenciant d'autres langages synchrones, et l'interface de programmation qui le connecte avec le langage hôte. Dans les parties trois et quatre, nous présentons la méthode de compilation utilisée, GRC, pour GraphCode, qui produit un graphe de flot de contrôle à partir du programme synchrone source. On revient sur la structure du GRC, les règles permettant de le construire, ainsi que notre méthode d'ordonnancement statique. Nous décrivons ensuite la génération de l'environnement d'exécution d'un programme synchrone dans le programme hôte. Dans une cinquième partie, nous montrons l'intérêt de la programmation synchrone dans le client et en quoi son modèle d'exécution s'adapte naturellement à celui du navigateur Web. Nous montrons qu'il est possible de profiter de cet avantage pour réagir aux évènements plus efficacement sans efforts d'optimisation. Avant de conclure, nous présentons de multiples exemples implémentés en Pendulum pour mettre en avant les qualités d'expressivité et de sûreté de la programmation synchrone sur différentes problématiques impliquant du multimédia et des interactions. / The goal of this thesis is to bring new capabilities to Web programming, whose languages, frameworks don't handle all the problematics raised by interactions in a Web application. Our solution is a programming language, Pendulum, taking its roots in synchronous reactive model à la Esterel. It brings safety and expressiveness, especially when handling multiple interactions. In the first chapter, we give our point of view on what is Web programming today, from the standard to the newest frameworks trying to fill programers needs by other approaches, like multitier programming or dataflow programming. In the second chapter, we introduce Pendulum and its instructions, its interface with the host language, and what it brings to both synchronous and Web programming. In the third and fourth chapter, we present the compilation method, GRC a.k.a GraphCode, that produces a control flow graph from the source code. In the first part, we insist mainly on GRC structure, the rules describing its creation and our technic to linearize parallel branches. Then, we describe the how to initialize synchronous execution environment in OCaml. In the fifth chapter, we show why it is a benefit to use synchronous programming in client programming and how its execution model can natively match the Web browser execution model. We use those ideas to show how a synchronous program can be fast to handle events without optimisation attempt. Before we conclude, we detail several examples implemented with our language to show how expressive and safe synchronous programming can be on diverse programs, implying multimedia and interactions.
|
8 |
Transformace Windows PE do grafu toku řízení / Windows PE Transformation into Control Flow GraphJirák, Ota Unknown Date (has links)
This thesis is interested in format of executable files EXE. It is focused on parts relevant for reverse engineering. It is interested in assembler, binary representation of instruction and disassembling. Follow I introduce converting from executables to control flow graph, basic structures (branches, cycles) detection.
|
9 |
Alternating Control Flow Graph Reconstruction by Combining Constant Propagation and Strided Intervals with Directed Symbolic Execution / Alternerande kontrollflödesgrafsrekonstruktion genom att kombinera propagerande av konstanter och klivande intervaller med riktad symbolisk exekveringPeterson, Thomas January 2019 (has links)
In this thesis we address the problem of control flow reconstruction in the presence of indirect jumps. We introduce an alternating approach which combines both overand under-approximation to increase the precision of the reconstructed control flow automaton compared to pure over-approximation. More specifically, the abstract interpretation based tool, Jakstab, from earlier work by Kinder, is used for the over-approximation. Furthermore, directed symbolic execution is applied to under-approximate successors of instructions when these can not be over-approximated precisely. The results of our experiments show that our approach can improve the precision of the reconstructed CFA compared to only using Jakstab. However, they reveal that our approach consumes a large amount of memory since it requires extraction and temporary storage of a large number of possible paths to the unresolved locations. As such, its usability is limited to control flow automatas of limited complexity. Further, the results show that strided interval analysis suffers in performance when encountering particularly challenging loops in the control flow automaton. / I detta examensarbete studeras hur rekonstruktion av kontrollflöde kan utföras i närvaro av indirekta hoppinstruktioner. I examensarbetet introduceras ett alternerande tillvägagångssätt som kombinerar både överoch underapproximation för att öka precisionen av den rekonstruerade kontrollflödesautomaten jämfört med endast överapproximation. Mer specifikt används det abstrakta tolknings-baserade verktyget, Jakstab, tidigare utvecklat av Kinder, för överapproximation. Vidare nyttjas riktad symbolisk exekvering för att underapproximera efterträdare till instruktioner när dessa inte kunnat överapproximeras med hög precision. Resultaten av våra experiment visar att vårt tillvägagångssätt kan förbättra precisionen hos den rekonstruerade kontrollflödesautomaten jämfört med att endast använda Jakstab. Dock visar de att vårt tillvägagångssätt kan fordra en stor mängd minne då det kräver extraktion och tillfällig lagring av ett stort antal möjliga vandringar från programmets ingång till de olösta programpositionerna. Därmed är dess användbarhet limiterad till kontrollflödesautomater av begränsad complexitet. Vidare visar resultaten av våra experiment även att analyser baserade på klivande intervaller tappar i prestanda när de möter en vis typ av loopar i kontrollflödesautomaten.
|
10 |
Cache Prediction and Execution Time Analysis on Real-Time MPSoCNeikter, Carl-Fredrik January 2008 (has links)
<p>Real-time systems do not only require that the logical operations are correct. Equally important is that the specified time constraints always are complied. This has successfully been studied before for mono-processor systems. However, as the hardware in the systems gets more complex, the previous approaches become invalidated. For example, multi-processor systems-on-chip (MPSoC) get more and more common every day, and together with a shared memory, the bus access time is unpredictable in nature. This has recently been resolved, but a safe and not too pessimistic cache analysis approach for MPSoC has not been investigated before. This thesis has resulted in designed and implemented algorithms for cache analysis on real-time MPSoC with a shared communication infrastructure. An additional advantage is that the algorithms include improvements compared to previous approaches for mono-processor systems. The verification of these algorithms has been performed with the help of data flow analysis theory. Furthermore, it is not known how different types of cache miss characteristic of a task influence the worst case execution time on MPSoC. Therefore, a program that generates randomized tasks, according to different parameters, has been constructed. The parameters can, for example, influence the complexity of the control flow graph and average distance between the cache misses.</p>
|
Page generated in 0.0544 seconds