Most current approaches to software verification are one-sided -- a safety prover will try to prove that a program is safe, while a bug-finding tool will try to find bugs. It is rare to find an analyser that is optimised for both tasks, which is problematic since it is hard to know in advance whether a program you wish to analyse is safe or not. The result of taking a one-sided approach to verification is false alarms: safety provers will often claim that safe programs have errors, while bug-finders will often be unable to find errors in unsafe programs. Orthogonally, many software verifiers are designed for reasoning about idealised programming languages that may not have widespread use. A common assumption made by verification tools is that program variables can take arbitrary integer values, while programs in most common languages use fixed-width bitvectors for their variables. This can have a real impact on the verification, leading to incorrect claims by the verifier. In this thesis we will show that it is possible to analyse C programs without generating false alarms, even if they contain unbounded loops, use non-linear arithmetic and have integer overflows. To do this, we will present two classes of analysis based on underapproximate loop acceleration and second-order satisfiability respectively. Underapproximate loop acceleration addresses the problem of finding deep bugs. By finding closed forms for loops, we show that deep bugs can be detected without unwinding the program and that this can be done without introducing false positives or masking errors. We then show that programs accelerated in this way can be optimised by inlining trace automata to reduce their reachability diameter. This inlining allows acceleration to be used as a viable technique for proving safety, as well as finding bugs. In the second part of the thesis, we focus on using second-order logic for program analysis. We begin by defining second-order SAT: an extension of propositional SAT that allows quantification over functions. We show that this problem is NEXPTIME-complete, and that it is polynomial time reducible to finite-state program synthesis. We then present a fully automatic, sound and complete algorithm for synthesising C programs from a specification written in C. Our approach uses a combination of bounded model checking, explicit-state model checking and genetic programming to achieve surprisingly good performance for a problem with such high complexity. We conclude by using second-order SAT to precisely and directly encode several program analysis problems including superoptimisation, de-obfuscation, safety and termination for programs using bitvector arithmetic and dynamically allocated lists.

abstract: Reverse engineering is critical to reasoning about how a system behaves. While complete access to a system inherently allows for perfect analysis, partial access is inherently uncertain. This is the case foran individual agent in a distributed system. Inductive Reverse Engineering (IRE) enables analysis under such circumstances. IRE does this by producing program spaces consistent with individual input-output examples for a given domain-specific language. Then, IRE intersects those program spaces to produce a generalized program consistent with all examples. IRE, an easy to use framework, allows this domain-specific language to be specified in the form of Theorist s, which produce Theory s, a succinct way of representing the program space. Programs are often much more complex than simple string transformations. One of the ways in which they are more complex is in the way that they follow a conversation-like behavior, potentially following some underlying protocol. As a result, IRE represents program interactions as Conversations in order to more correctly model a distributed system. This, for instance, enables IRE to model dynamically captured inputs received from other agents in the distributed system. While domain-specific knowledge provided by a user is extremely valuable, such information is not always possible. IRE mitigates this by automatically inferring program grammars, allowing it to still perform efficient searches of the program space. It does this by intersecting conversations prior to synthesis in order to understand what portions of conversations are constant. IRE exists to be a tool that can aid in automatic reverse engineering across numerous domains. Further, IRE aspires to be a centralized location and interface for implementing program synthesis and automatic black box analysis techniques. / Dissertation/Thesis / Masters Thesis Computer Science 2019

We consider the problem of synthesizing program inverses for imperative languages. Our primary motivation comes from optimistic parallel discrete event simulation (OPDES). There, a simulator must process events while respecting logical temporal event-ordering constraints; to extract parallelism, an OPDES simulator may speculatively execute events and only rollback execution when event-ordering violations occur. In this context, the ability to perform rollback by running time- and space-efficient reverse programs, rather than saving and restoring large amounts of state, can make OPDES more practical. Synthesizing inverses also appears in numerous other software engineering contexts, such as debugging, synthesizing “undo” code, or even generating decompressors automatically given only lossless compression code. This thesis mainly contains three chapters. In the first chapter, we focus on handling programs with only scalar data and arbitrary control flows. By building a value search graph (VSG) that represents recoverability relationships between variable values, we turn the problem of recovering previous values into a graph search one. Forward and reverse programs are generated according to the search results. For any loop that produces an output state given a particular input state, our method can synthesize an inverse loop that reconstructs the input state given the original loop's output state. The synthesis process consists of two major components: (a) building the inverse loop's body, and (b) building the inverse loop's predicate. Our method works for all natural loops, including those that take early exits (e.g., via breaks, gotos, returns). In the second chapter we extend our method to handling programs containing arrays. Based on Array SSA, we develop a modified Array SSA from which we could easily build equalities between arrays and array elements. Specifically, to represent the equality between two arrays, we employ the array subregion as the constraint. During the search those subregions will be calculated to guarantee that all array elements will be retrieved. We also develop a demand-driven method to retrieve array elements from a loop, in which each time we only try to retrieve an array element from an iteration if that element has not been modified in previous iterations. To ensure the correctness of each retrieval, the boundary conditions are created and checked at the entry and the exit of the loop. In the last chapter, we introduce several techniques of handling high-level constructs of C++ programs, including virtual functions, copying C++ objects, C++ STL containers, C++ source code normalization, inter-procedural function calls, etc. Since C++ is an object-oriented (OO) language, our discussion in this chapter can also be extended to other OO languages like Java.

Programming has advanced a great deal since the appearance of the stored-program architecture. Through the successive generations of machine codes, assembly languages, high-level languages, and object-oriented languages, the drive has been toward program descriptions that express more meaning in a shorter space. This trend continues today with domain-specific languages. However, conventional languages rely on a textual formalism (commands, statements, lines of code) to capture the programmer's intent, which, regardless of its level of abstraction, imposes inevitable overheads. Before successful programming activities can take place, the syntax has to be mastered, names and keywords memorized, the library routines mastered, etc. Existing visual programming languages avoid some of these overheads, but do not release the programmer from the task of specifying the program logic, which consumes the main portion of programming time and also is the major source of difficult bugs. Our work aims to minimize the demands a formalism imposes on the programmer of geometric subroutines other than what is inherent in the problem itself. Our approach frees the programmer from syntactic constraints and generates logically correct programs automatically from program descriptions in the form of diagrams. To write a program, the programmer simply draws a few diagrams to depict the problem context and specifies all the necessary parameters through menu operations. Diagrams are succinct, easy to learn, and intuitive to use. They are much easier to modify than code, and they help the user visualize and analyze the problem, in addition to providing information to the computer. Furthermore, diagrams describe a situation rather than a task and thus are reusable for different tasks—in general, a single diagram can generate many programs. For these reasons, we have chosen diagrams as the main specification mechanism. In addition, we leverage the power of automatic inference to reason about diagrams and generic components—the building blocks of our programs—and discover the logic for assembling these components into correct programs. To facilitate inference, symbolic facts encode entities present in the diagrams, their spatial relationships, and the preconditions and effects of reusable components. We have developed a reference implementation and tested it on a number of real-world examples to demonstrate the feasibility and efficacy of our approach. / text

No description available.

No description available.

Software systems are ubiquitous in today's world and yet, remain vulnerable to the fallibility of human programmers as well as the unpredictability of their operating environments. The overarching goal of this dissertation is to develop algorithms to enable automated and efficient design and analysis of reliable programs. In the first and second parts of this dissertation, we focus on the development of programs that are free from programming errors. The intent is not to eliminate the human programmer, but instead to complement his or her expertise, with sound and efficient computational techniques, when possible. To this end, we make contributions in two specific domains. Program debugging --- the process of fault localization and error elimination from a program found to be incorrect --- typically relies on expert human intuition and experience, and is often a lengthy, expensive part of the program development cycle. In the first part of the dissertation, we target automated debugging of sequential programs. A broad and informal statement of the (automated) program debugging problem is to suitably modify an erroneous program, say P, to obtain a correct program, say P'. This problem is undecidable in general; it is hard to formalize; moreover, it is particularly challenging to assimilate and mechanize the customized, expert programmer intuition involved in the choices made in manual program debugging. Our first contribution in this domain is a methodical formalization of the program debugging problem, that enables automation, while incorporating expert programmer intuition and intent. Our second contribution is a solution framework that can debug infinite-state, imperative, sequential programs written in higher-level programming languages such as C. Boolean programs, which are smaller, finite-state abstractions of infinite-state or large, finite-state programs, have been found to be tractable for program verification. In this dissertation, we utilize Boolean programs for program debugging. Our solution framework involves two main steps: (a) automated debugging of a Boolean program, corresponding to an erroneous program P, and (b) translation of the corrected Boolean program into a correct program P'. Shared-memory concurrent programs are notoriously difficult to write, verify and debug; this makes them excellent targets for automated program completion, in particular, for synthesis of synchronization code. Extant work in this domain has focused on either propositional temporal logic specifications with simplistic models of concurrent programs, or more refined program models with the specifications limited to just safety properties. Moreover, there has been limited effort in developing adaptable and fully-automatic synthesis frameworks that are capable of generating synchronization at different levels of abstraction and granularity. In the second part of this dissertation, we present a framework for synthesis of synchronization for shared-memory concurrent programs with respect to temporal logic specifications. In particular, given a concurrent program composed of synchronization-free processes, and a temporal logic specification describing their expected concurrent behaviour, we generate synchronized processes such that the resulting concurrent program satisfies the specification. We provide the ability to synthesize readily-implementable synchronization code based on lower-level primitives such as locks and condition variables. We enable synchronization synthesis of finite-state concurrent programs composed of processes that may have local and shared variables, may be straight-line or branching programs, may be ongoing or terminating, and may have program-initialized or user-initialized variables. We also facilitate expression of safety and liveness properties over both control and data variables by proposing an extension of propositional computation tree logic. Most program analyses, verification, debugging and synthesis methodologies target traditional correctness properties such as safety and liveness. These techniques typically do not provide a quantitative measure of the sensitivity of a computational system's behaviour to unpredictability in the operating environment. We propose that the core property of interest in reasoning in the presence of such uncertainty is robustness --- small perturbations to the operating environment do not change the system's observable behavior substantially. In well-established areas such as control theory, robustness has always been a fundamental concern; however, the techniques and results therein are not directly applicable to computational systems with large amounts of discretized, discontinuous behavior. Hence, robustness analysis of software programs used in heterogeneous settings necessitates development of new theoretical frameworks and algorithms. In the third part of this dissertation, we target robustness analysis of two important classes of discrete systems --- string transducers and networked systems of Mealy machines. For each system, we formally define robustness of the system with respect to a specific source of uncertainty. In particular, we analyze the behaviour of transducers in the presence of input perturbations, and the behaviour of networked systems in the presence of channel perturbations. Our overall approach is automata-theoretic, and necessitates the use of specialized distance-tracking automata for tracking various distance metrics between two strings. We present constructions for such automata and use them to develop decision procedures based on reducing the problem of robustness verification of our systems to the problem of checking the emptiness of certain automata. Thus, the system under consideration is robust if and only if the languages of particular automata are empty. / text

Submitted by Lucienne Costa (lucienneferreira@ufcg.edu.br) on 2018-09-13T20:44:41Z No. of bitstreams: 1 REUDISMAM ROLIM DE SOUSA – TESE (PPGCC) 2018.pdf: 4395945 bytes, checksum: 2241c8bad2cdc8eda86eb53c2e64c227 (MD5) / Made available in DSpace on 2018-09-13T20:44:41Z (GMT). No. of bitstreams: 1 REUDISMAM ROLIM DE SOUSA – TESE (PPGCC) 2018.pdf: 4395945 bytes, checksum: 2241c8bad2cdc8eda86eb53c2e64c227 (MD5) Previous issue date: 2018-08-02 / Capes / Ferramentas como ErrorProne, ReSharper e PMD ajudam os programadores a detectar e/ou remover automaticamente vários padrões de códigos suspeitos, possíveis bugs ou estilo de código incorreto. Essas regras podem ser expressas como quick fixes que detectam e reescrevem padrões de código indesejados. No entanto, estender seus catálogos de regras é complexo e demorado. Nesse contexto, os programadores podem querer executar uma edição repetitiva automaticamente para melhorar sua produtividade, mas as ferramentas disponíveis não a suportam. Além disso, os projetistas de ferramentas podem querer identificar regras úteis para automatizarem. Fenômeno semelhante ocorre em sistemas de tutoria inteligente, onde os instrutores escrevem transformações complicadas que descrevem "falhas comuns" para consertar submissões semelhantes de estudantes a tarefas de programação. Nesta tese, apresentamos duas técnicas. REFAZER, uma técnica para gerar automaticamente transformações de programa. Também propomos REVISAR, nossa técnica para aprender quick fixes em repositórios. Nós instanciamos e avaliamos REFAZER em dois domínios. Primeiro, dados exemplos de edições de código dos alunos para corrigir submissões de tarefas incorretas, aprendemos transformações para corrigir envios de outros alunos com falhas semelhantes. Em nossa avaliação em quatro tarefas de programação de setecentos e vinte alunos, nossa técnica ajudou a corrigir submissões incorretas para 87% dos alunos. No segundo domínio, usamos edições de código repetitivas aplicadas por desenvolvedores ao mesmo projeto para sintetizar a transformação de programa que aplica essas edições a outros locais no código. Em nossa avaliação em 56 cenários de edições repetitivas de três grandes projetos de código aberto em C#, REFAZER aprendeu a transformação pretendida em 84% dos casos e usou apenas 2.9 exemplos em média. Para avaliar REVISAR, selecionamos 9 projetos e REVISAR aprendeu 920 transformações entre projetos. Atuamos como projetistas de ferramentas, inspecionamos as 381 transformações mais comuns e classificamos 32 como quick fixes. Para avaliar a qualidade das quick fixes, realizamos uma survey com 164 programadores de 124 projetos, com os 10 quick fixes que apareceram em mais projetos. Os programadores suportaram 9 (90%) quick fixes. Enviamos 20 pull requests aplicando quick fixes em 9 projetos e, no momento da escrita, os programadores apoiaram 17 (85%) e aceitaram 10 delas. / Tools such as ErrorProne, ReSharper, and PMD help programmers by automatically detecting and/or removing several suspicious code patterns, potential bugs, or instances of bad code style. These rules could be expressed as quick fixes that detect and rewrite unwanted code patterns. However, extending their catalogs of rules is complex and time-consuming. In this context, programmers may want to perform a repetitive edit into their code automatically to improve their productivity, but available tools do not support it. In addition, tool designers may want to identify rules helpful to be automated. A similar phenomenon appears in intelligent tutoring systems where instructors have to write cumbersome code transformations that describe “common faults” to fix similar student submissions to programming assignments. In this thesis, we present two techniques. REFAZER, a technique for automatically generating program transformations. We also propose REVISAR, our technique for learning quick fixes from code repositories. We instantiate and evaluate REFAZER in two domains. First, given examples of code edits used by students to fix incorrect programming assignment submissions, we learn program transformations that can fix other students’ submissions with similar faults. In our evaluation conducted on four programming tasks performed by seven hundred and twenty students, our technique helped to fix incorrect submissions for 87% of the students. In the second domain, we use repetitive code edits applied by developers to the same project to synthesize a program transformation that applies these edits to other locations in the code. In our evaluation conducted on 56 scenarios of repetitive edits taken from three large C# open-source projects, REFAZER learns the intended program transformation in 84% of the cases and using only 2.9 examples on average. To evaluate REVISAR, we select 9 projects, and REVISAR learns 920 transformations across projects. We acted as tool designers, inspected the most common 381 transformations and classified 32 as quick fixes. To assess the quality of the quick fixes, we performed a survey with 164 programmers from 124 projects, showing the 10 quick fixes that appeared in most projects. Programmers supported 9 (90%) quick fixes. We submitted 20 pull requests applying our quick fixes to 9 projects and, at the time of the writing, programmers supported 17 (85%) and accepted 10 of them.

[pt] Garantir que programas são implementados de forma a cumprir uma especificação é uma questão fundamental em computação, por isso, têm sido propostos vários métodos que almejam provar a correção dos programas. Este trabalho apresenta um método, baseado no isomorfismo de Curry-Howard, que extrai conteúdos computacionais de provas intuicionistas, conhecido como síntese construtiva ou proofs-as-programs. É proposto um processo de síntese construtiva de programas, onde a extração do conteúdo computacional gera um programa em linguagem imperativa a partir de uma prova em lógica intuicionista poli-sortida, cujos axiomas definem os tipos abstratos de dados, sendo utilizado como sistema dedutivo a Dedução Natural. Também é apresentada uma prova de correção, bem como uma prova de completude do método atráves do uso de um sistema com regra ômega (computacional) para a aritmética de Heyting, concluindo com uma demonstração da relação entre o uso da indução finita no lugar da regra ômega computacional no processo de síntese. / [en] One of the main problems in computer science is to assure that programs are implemented in such a way that they satisfy a given specification. There are many studies about methods to prove correctness of programs. This work presents a method, belonging to the constructive synthesis or proofs-as-programs paradigm, that comes from the Curry- Howard isomorphism and extracts the computational contents of intuitionist proofs. The synthesis process proposed produces a program in an imperative language from a proof in many-sorted intuitionist logic, where the axioms define the abstract data types using Natural Deduction as deductive system. It is proved the correctness, as well as the completeness of the method regarding the Heyting arithmetic with ômega-rule(in its computational version). A discussion about the use of the finitary induction instead of computational ômega-rule concludes the work.

The Hybrid Electric Vehicle (HEV) is a complex electromechanical system with complex interactions among various components. Due to the large number of design variables involved, the design flexibility in the HEV makes performance studies difficult. As the system complexity and sophistication increases, it becomes much more difficult to predict these interactions and design the system accordingly. Also, different variations in the design and manufacture of various components and systems involve a large amount of work and cost to keep updated of all these variations. While the above issues ask for a flexible design environment suitable for vehicle design, most of the existing powertrain design tools are based on experiential models, such as look-up tables, which use idealized assumptions and limited experimental data. The accuracy of the results produced by these tools is not good enough for designing these new generation vehicles. Also, sometimes the designs may lead to components or systems beyond physical limitations. To make the powertrain design more efficient, the models developed must be closely related to the underlying physics of the components. Only such physics-based models can facilitate high fidelity simulations for dynamics at different time scales. This results in the quest for a design tool that manages the vehicle?s development process while maintaining tight integration between the software and physical artifacts. The thesis addresses the above issues and focuses on the modeling of HEV using model integrated computing and employing physics-based resistive companion form modeling method. For this purpose, Generic Modeling Environment (GME), software developed by Institute of Software and Integrated Systems (ISIS), Vanderbilt University is used as the platform for developing the models. A modeling environment for hybrid vehicle design is prepared and a Battery Electric Vehicle (BEV) is developed as an application of the developed environment. Resistive companion form models of various BEV components are prepared and a model interpreter is prepared for integrating the developed component models and simulating the design.