This paper presents an algorithm to automatically infer a recursive state machine (RSM) describing the space of acceptable input of an arbitrary binary program by executing that program with one or more valid inputs. The algorithm automatically identifies atomic fields of fixed and variable lengths and syntactic elements, such as separators and terminators, and generalizes them into regular expression tokens. It constructs an RSM of tokens to represent structures such as arrays and records. Further, it constructs nested states in the RSM to represent complex, nested structures. The RSM may serve as an independent parser for the program's acceptable inputs. A controlled experiment was performed using a prototype implementation of the algorithm and a set of synthetic programs with input formats that mimic characteristics of conventional data formats, such as CSV, PNG, PE file, etc. The experiment demonstrates that the inferred RSMs correctly identify the syntactic elements and their grammatical orderings. When used as generators, the RSMs also produced syntactically correct data for the formats that use terminators to end a sequence of elements, but not so when the format maintains a count of elements for variable length fields instead of a terminator. Experiments with real-world programs produced similar results.

The identification of similar functions in malware assists analysis by supporting the exclusion of functions that have been previously analysed, allows the identification of new variants, supports authorship attribution, and the analysis of malware phylogeny. A function's context is a set comprising the function itself and all the program functions that may be executed when this function is called. Contextual features consist of data that is extracted from the functions contained in the function context. This paper presents a novel technique called Cross Version Contextual Function Similarity (CVCFS) to identify function pairs in two programs using features based on both individual functions and function context. The CVCFS technique uses Support Vector Machine (SVM) machine learning of function similarity features to pre-filter function pairs and then applies an edit distance technique using function semantics to reduce false positives. A case study is provided where individual and contextual features are extracted from three versions of Zeus malware. The SVM pre-filtering, followed by the use of an edit distance technique to filter false positives, gives a function pair identification accuracy of 85 percent.

We introduce a model for mixed syntactic/semantic approximation of programs based on symbolic finite automata (SFA). The edges of SFA are labeled by predicates whose semantics specifies the denotations that are allowed by the edge. We introduce the notion of abstract symbolic finite automaton (ASFA) where approximation is made by abstract interpretation of symbolic finite automata, acting both at syntactic (predicate) and semantic (denotation) level. We investigate in the details how the syntactic and semantic abstractions of SFA relate to each other and contribute to the determination of the recognized language. Then we introduce a family of transformations for simplifying ASFA. We apply this model to prove properties of commonly used tools for similarity analysis of binary executables. Following the structure of their control flow graphs, disassembled binary executables are represented as (concrete) SFA, where states are program points and predicates represent the (possibly infinite) I/O semantics of each basic block in a constraint form. Known tools for binary code analysis are viewed as specific choices of symbolic and semantic abstractions in our framework, making symbolic finite automata and their abstract interpretations a unifying model for comparing and reasoning about soundness and completeness of analyses of low-level code.

A method for context-sensitive analysis of binaries that may have obfuscated procedure call and return operations is presented. Such binaries may use operators to directly manipulate stack instead of using native call and ret instructions to achieve equivalent behavior. Since definition of context-sensitivity and algorithms for context-sensitive analysis have thus far been based on the specific semantics associated to procedure call and return operations, classic interprocedural analyses cannot be used reliably for analyzing programs in which these operations cannot be discerned. A new notion of context-sensitivity is introduced that is based on the state of the stack at any instruction. While changes in `calling'-context are associated with transfer of control, and hence can be reasoned in terms of paths in an interprocedural control flow graph (ICFG), the same is not true of changes in 'stack'-context. An abstract interpretation based framework is developed to reason about stack-contexts and to derive analogues of call-strings based methods for the context-sensitive analysis using stack-context. The method presented is used to create a context-sensitive version of Venable et al.'s algorithm for detecting obfuscated calls. Experimental results show that the context-sensitive version of the algorithm generates more precise results and is also computationally more efficient than its context-insensitive counterpart.

Information about calls to the operating system (or kernel libraries) made by a binary executable may be used to determine whether the binary is malicious. Being aware of this approach, malicious programmers hide this information by making such calls without using the call instruction. For instance, the call addr instruction may be replaced by two push instructions and a ret instruction, the first push pushes the address of instruction after the ret instruction, and the second push pushes the address addr. The code may be further obfuscated by spreading the three instructions and by splitting each instruction into multiple instructions. This work presents a method to statically detect obfuscated calls in binary code. The idea is to use abstract interpretation to detect where the normal call-ret convention is violated. These violations can be detected by what is called an abstract stack graph. An abstract stack graph is a concise representation of all potential abstract stacks at every point in a program. An abstract stack is used to associate each element in the stack to the instruction that pushes the element. An algorithm for constructing the abstract stack graph is also presented. Methods for using the abstract stack graph are shown to detect eight different obfuscations. The technique is demonstrated by implementing a prototype tool called DOC (detector for obfuscated calls).

The cohesion or strength of a component of a software system is an indicator of its maintainability. The most popular way—as evidenced from coverage in textbooks—of determining the cohesion of a component is a set of rules developed by Stevens, Myers, Constantine and Yourdon in the early 1970s. Using Stevens et al.'s approach, a component is assigned one of seven levels of cohesion. This paper presents the results of an experiment analysing these rules of cohesion. The experiment, using fifteen computer science graduate students as subjects, was conducted to assess whether Stevens et al.'s rules were objective, i.e., whether there is a better-than-chance agreement in the cohesion levels assigned by different programmers. The data, though preliminary due to the small sample size, indicate that there is a significant variation in the cohesion levels assigned by them even though the subjects were assessed to have understood the concepts well. This decoupling between the understanding of the concepts of the scale and of the use of the scale in proper fashion is intriguing and deserves further study. The results also raise questions about the precision of the material taught in the software engineering curriculum. Copyright © 1999 John Wiley & Sons, Ltd.

It is difficult to debug a program when the data set that causes it to fail is large (or voluminous). The cues that may help in locating the fault are obscured by the large amount of information that is generated from processing the data set. Clearly, a smaller data set which exhibits the same failure should lead to the diagnosis of the fault more quickly than the initial, large data set. We term such a smaller data set a data slice and the process of creating it data slicing. The problem of creating a data slice is undecidable. In this paper, we investigate four generate-and-test heuristics for deriving a smaller data set that reproduces the failure exhibited by a large data set. The four heuristics are: invariance analysis, origin tracking, random elimination and program-specific heuristics. We also provide a classification of programs based upon a certain relationship between their input and output. This classification may be used to choose an appropriate heuristic in a given debugging scenario. As evidence from a database of debugging anecdotes at the Open University, U.K., debugging failures exhibited by large data sets require inordinate amounts of time. Our data slicing techniques would significantly reduce the effort required in such scenarios. © 1998 John Wiley & Sons, Ltd.

This paper makes a contribution to the calculational paradigm of program development, a paradigm in which programs are calculated from their specifications by applying meaning preserving transformations. It introduces program induction, a technique analogous to mathematical induction, and iteration folding, a refinement rule. Using program induction, a specification is decomposed into a base case and an inductive case and their solutions are sequentially composed to derive the final program. The iteration folding rule is applied to transform potentially infinite nested if statements into a while statement. Our technique and rule augment the existing repertoire of techniques and rules in the calculus of program refinement.

Article Constructing call multigraphs using dependence graphs Share on Author: Arun Lakhotia View Profile Authors Info & Claims POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesMarch 1993 Pages 273–284https://doi.org/10.1145/158511.158647Online:01 March 1993Publication History 22citation351DownloadsMetricsTotal Citations22Total Downloads351Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access