TY - THES TI - Data Structure Identification from Executions of Pointer Programs AU - Rupprecht, Thomas PY - 2020 PB - University of Bamberg Press CY - Bamberg T3 - Schriften aus der Fakultät Wirtschaftsinformatik und Angewandte Informatik der Otto-Friedrich-Universität Bamberg SN - 978-3-86309-717-2 DO - 10.20378/irb-47325 UR - https://fis.uni-bamberg.de/handle/uniba/47325 LA - eng AB - The reverse engineering of binaries is a tedious and time consuming task, yet mandatory when the need arises to understand the behaviour of a program for which source code is unavailable. Instances of source code loss for old arcade games [1] and the steadily growing amount of malware [2] are prominent use cases requiring reverse engineering. One of the challenges when dealing with binaries is the loss of low level type information, i.e., primitive and compound types, which even state-of-the-art type recovery tools often cannot reconstruct with full accuracy. Further programmers most commonly use high level data structures, such as linked lists, in addition to primitive types. Therefore detection of dynamic data structure shapes is an important aspect of reverse engineering. Though the recognition of dynamic data structure shapes in the presence of tricky programming concepts such as pointer arithmetic and casts – which are both fundamental concepts to enable, e.g., the frequently used Linux kernel list [3] – also bring current shape detection tools to their limits. A recent approach called Data Structure Investigator (DSI) [4] , aims for the detection of dynamic pointer based data structures. While the approach is general in nature, a concrete realization for C programs requiring source code is envisioned as programming constructs such as type casts and pointer arithmetic will stress test the approach. Therefore, the first research question addressed in this dissertation is whether DSI can meet its goal in the presence of the sheer multitude of existing data structure implementations. The second research question is whether DSI can be opened up to reverse engineer C/C++ binaries, even in the presence of type information loss and the variety of C/C++ programming constructs. Both questions are answered positively in this dissertation. The first is answered by realizing the DSI source code approach, which requires detailing fundamental aspects of DSI’s theory to arrive at a working implementation, e.g., handling the consistency of DSI’s memory abstraction and quantifying the interconnections found within a dynamic pointer based data structure, e.g., a parent child nesting scenario, to allow for its detection. DSI’s utility is evaluated on an extensive benchmark including real world examples (libusb [5], bash [6]) and shape analysis examples, [7,8] . The second question is answered through the development of a DSI prototype for binaries (DSIbin). To compensate for the loss of perfect type information found in source code, DSIbin interfaces with the state-of-the-art type recovery tool Howard [9]. Notably, DSIbin improves upon type information recovered by Howard. This is accomplished through a much improved nested struct detection and type merging algorithm, both of which are fundamental aspects for the reverse engineering of binaries. The proposed approach is again evaluated by a diverse benchmark containing real world examples such as, the VNC clipping library, The Computer Language Benchmarks Game and the Olden Benchmark, as well as examples taken from the shape analysis literature. In summary, this dissertation improves upon the state-of-the-art of shape detection and reverse engineering by (i) realizing and evaluating the DSI approach, which includes contributing to DSI’s theory and results in the DSI prototype; (ii) opening up DSI for C/C++ binaries so as to extend DSI to reverse engineering, resulting in the DSIbin prototype; (iii) handling data structures with DSIbin not covered by some related work such as skip lists; (iv) refining the nesting detection and performing type merging for types excavated by Howard. Further, DSIbin’s ultimate future use case of malware analysis is hardened by revealing the presence of dynamic data structures in multiple real world malware samples. In summary, this dissertation advanced the dynamic analysis of data structure shapes with the aforementioned contributions to the DSI approach for source code and further by transferring this new technology to the analysis of binaries. The latter resulted in the additional insight that high level dynamic data structure information can help to infer low level type information. 1. http://kotaku.com/5028197/sega-cant-find-the-source-code-for-your-favorite-old-school-arcade-games 2. https://www.av-test.org/en/statistics/malware/ 3. https://github.com/torvalds/linux/blob/master/include/linux/list.h 4. SWT Research Group, University Bamberg, DFG-Project LU 1748/4-1 5. http://libusb.info/ 6. https://www.gnu.org/software/bash/ 7. Predator: http://www.fit.vutbr.cz/research/groups/verifit/tools/predator/ 8. Forester: http://www.fit.vutbr.cz/research/groups/verifit/tools/forester/ 9. http://www.cs.vu.nl/ herbertb/papers/dde_ndss11-preprint.pdf KW - Data structure identification; Dynamic data structures; Pointer programs; Reverse engineering; Type recovery ER - TY - THES TI - Reverse Engineering of Real-Time System Models From Event Trace Recordings AU - Sailer, Andreas PY - 2019 PB - University of Bamberg Press CY - Bamberg T3 - Schriften aus der Fakultät Wirtschaftsinformatik und Angewandte Informatik der Otto-Friedrich-Universität Bamberg SN - 978-3-86309-690-8 DO - 10.20378/irb-46506 UR - https://fis.uni-bamberg.de/handle/uniba/46506 LA - eng AB - Model-driven approaches are experiencing an increasing acceptance in the automotive domain thanks to the availability of the AUTOSAR standard, which defines an open software architecture for the model-based development of real-time systems and a corresponding development methodology. However, the process of creating models of existing system components is often difficult and time consuming, especially when legacy code is involved or information about the exact timing is needed. The research community tackles this problem by developing algorithms for automatically deriving characteristics of the system’s timing behaviour, e.g., response times and resource blockings from various artefacts such as source code or runtime measurements. This work focuses on reversely engineering an AUTOSAR-compliant model, which can be used for further processing including timing simulation and optimisation, via a dynamic analysis from trace recordings of a real-time system. Although software reverse engineering via dynamic analysis has a long history, little research targets embedded systems and its use for multi-core architectures is largely unresearched. Furthermore, related work mainly discusses the analysis of individual characteristics of a real-time system, such as execution times or stimulation patterns instead of creating a description of the entire system. Huselius, whose work is among the publications most related to the topic of this thesis, proposes a technique to reverse engineer a model that reflects the general temporal behaviour of the original real-time software. However, like other existing solutions, it was not developed with AUTOSAR in mind. It is also not feasible to make this approach applicable to the automotive domain, because Huselius has not considered some required details, such as activation patterns, scheduling information, and compliance to the standardised development methodology of AUTOSAR. We want to tackle this deficiency by introducing, in this work, an approach that seizes on Huselius’s considerations and extends them in order to make them applicable to the automotive domain. To do so, we present CoreTAna, a prototypical tool that derives an AUTOSAR compliant model of a real-time system by conducting dynamic analysis using trace recordings. Its reverse engineering approach is designed in such a way that it fits seamlessly into the methodology specified by AUTOSAR. CoreTAna’s current features are explained and their benefits for reverse engineering are highlighted, and a framework for evaluating the quality of synthesised models is described. Motivated by the challenge of assessing the quality of reverse engineered models of real-time software, we also introduce a mathematical measure for comparing trace recordings from embedded real-time systems regarding their temporal behaviour and a benchmark framework based on this measure, for evaluating reverse engineering tools such as CoreTAna. This framework considers common system architectures and also includes randomly generated systems and systems of projects in the automotive domain and other industries. Finally, CoreTAna’s performance and applicability are evaluated on the basis of this benchmark. KW - Modeling, Reverse Engineering, AUTOSAR ER - TY - THES TI - On the Automated Derivation of Domain-Specific UML Profiles AU - Kraas, Alexander PY - 2019 PB - University of Bamberg Press CY - Bamberg T3 - Schriften aus der Fakultät Wirtschaftsinformatik und Angewandte Informatik der Otto-Friedrich-Universität Bamberg SN - 978-3-86309-670-0 DO - 10.20378/irbo-54891 UR - https://fis.uni-bamberg.de/handle/uniba/45648 LA - eng AB - Similar to general-purpose languages, domain-specific languages (DSL) can be developed based on grammar formalisms, the model-driven engineering (MDE) is also becoming more and more important for the development of DSLs. On the one hand, metamodels can be used to define the syntax and semantics of DSLs. On the other hand, a DSL can be realized by adapting the Unified Modeling Language (UML) via the profiling mechanism, i.e., by defining a UML profile. For example, metamodels for a DSL can be created with the language concepts provided by the Meta Object Facility (MOF), distinguishing between the Essential MOF (EMOF) and the Complete MOF (CMOF). The latter variant is based on the EMOF but provides additional language concepts. A higher degree of abstraction and reuse of existing metamodels can be achieved by employing the language concepts provided by CMOF, which can be advantageous for the creation of more complex DSLs. Apart from DSLs proposed in the literature, a model-based specification of DSLs becomes increasingly important for standardization. Both metamodels and UML profiles are often provided for standardized DSLs. The mappings of metamodels to UML profiles are usually only specified in some abstract manner by such standards. Therefore, such mappings do not provide all the details required to create executable model transformations. Moreover, the static semantics of metamodels and/or UML profiles are usually specified only in natural language. Thus, on the one hand, ambiguities can occur, and on the other hand, the soundness of the static semantics cannot be verified and validated without a manual translation into a machine-processable language. The main goal of this dissertation is to remedy the identified weaknesses in developing DSLs, for which a CMOF-compliant metamodel and a UML profile shall be created. To achieve this goal, we propose a holistic MDE-based approach for automatically deriving UML profiles and model transformations based on CMOF metamodels. This approach enables an automatic transfer of DSL’s static semantics to UML profiles, so that the well-formedness of UML models with applied UML profile of a DSL can be verified automatically. In addition, the interoperability between UML and DSL models can already be validated in the development phase using the derived model transformations. Apart from new DSLs that are created from scratch, our approach also supports a migration of existing grammar-based DSLs towards CMOF-based metamodels, provided syntax rules exist. To verify and evaluate the presented derivation approach, we have implemented a toolchain that we used to conduct two case studies on the Specification and Description Language (SDL) and the Test Description Language (TDL). KW - Metamodeling KW - UML profiles KW - derivation KW - static semantics KW - OCL ER - TY - THES TI - Modal Interface Theories for Specifying Component-based Systems AU - Fendrich, Sascha PY - 2017 PB - opus CY - Bamberg UR - https://fis.uni-bamberg.de/handle/uniba/42329 LA - eng AB - Large software systems frequently manifest as complex, concurrent, reactive systems and their correctness is often crucial for the safety of the application. Hence, modern techniques of software engineering employ incremental, component-based approaches to systems design. These are supported by interface theories which may serve as specification languages and as semantic foundations for software product lines, web-services, the internet of things, software contracts and conformance testing. Interface theories enable a systems designer to express communication requirements of components on their environments and to reason about the mutual compatibility of these requirements in order to guarantee the communication safety of the system. Further, interface theories enrich traditional operational specification theories by declarative aspects such as conjunction and disjunction, which allow one to specify systems heterogeneously. However, substantial practical aspects of software verification are not supported by current interface theories, e.g., reusing components, adapting components to changed operational environments, reasoning about the compatibility of more than two components, modelling software product lines or tracking erroneous behaviour in safety-critical systems. The goal of this thesis is to investigate the theoretical foundations for making interface theories more practical by solving the above issues. Although partial solutions to some of these issues have been presented in the literature, none of them succeeds without sacrificing other desired features. The particular challenge of this thesis is to solve these problems simultaneously within a single interface theory. To this end, the arguably most general interface theory Modal Interface Automata (MIA) is extended, yielding the interface theory Error-preserving Modal Interface Automata (EMIA). The above problems are addressed as follows. Quotient operators are adjoint to composition and, therefore, support component reuse. Such a quotient operator is introduced to both MIA and EMIA. It is the first one that considers nondeterministic dividends and compatibility. Alphabet extension operators for MIA and EMIA allow for the change of operational environment by permitting one to adapt system components to new interactions without breaking previously satisfied requirements. Erroneous behavior is identified as a common source of problems with respect to the compatibility of more than two components, the modelling of software product lines and erroneous behaviour in safety-critical systems. EMIA improves on previous interface theories by providing a more precise semantics with respect to erroneous behaviour based on error-preservation. The relation between error-preservation and the usual error-abstraction employed in previous interface theories is investigated, establishing a Galois insertion from MIA into EMIA that is relevant at the levels of specifications, composition operations and proofs. The practical utility of interface theories is demonstrated by providing a software implementation of MIA and EMIA that is applied to two case studies. Further, an outlook is given on the relation between type checking and refinement checking. As a proof of concept, the simple interface theory Interface Automata is extended to a behavioural type theory where type checking is a syntactic approximation of refinement checking. ER -