System programming languages such as C and C++ are designed to give the programmer full control over the underlying hardware. However, this freedom comes at the cost of type and memory safety violations which may allow an attacker to compromise applications. In particular, type safety violation, also known as type confusion, is one of the major attack vectors to corrupt modern C++ applications. In the past years, several type confusion detectors have been proposed, but they are severely limited by high performance overhead, low detection coverage, and high false positive rates. To address these issues, we propose HexType and V-Type. First, we propose HexType, a tool that provides low-overhead disjoint metadata structures, compiler optimizations, and handles specific object allocation patterns. Thus, compared to prior work, HexType significantly improves detection coverage and reduces performance overhead. In addition, HexType discovers new type confusion bugs in real world programs such as Qt and Apache Xerces-C++. However, HexType still has considerable overhead from managing the disjoint metadata structure and tracking individual objects, and has false positives from imprecise object tracking, although HexType significantly reduces performance overhead and detection coverage. To address these issues, we propose a further advanced mechanism V-Type, which forcibly changes non-polymorphic types into polymorphic types to make sure all objects maintain type information. By doing this, V-Type removes the burden of tracking object allocation and deallocation and of managing a disjoint metadata structure, which reduces performance overhead and improves detection precision. Another major attack vector is memory safety violations, which attackers can take advantage of by accessing out of bound or deleted memory. For memory safety violation detection, combining a fuzzer with sanitizers is a popular and effective approach. However, we find that heavy metadata structure of current sanitizers hinders fuzzing effectiveness. Thus, we introduce FuZZan to optimize sanitizer metadata structures for fuzzing. Consequently, FuZZan improves fuzzing throughput, and this helps the tester to discover more unique paths given the same amount of time and to find bugs faster. In conclusion, my research aims to eliminate critical and common C/C++ memory and type safety violations through practical programming analysis techniques. For this goal, through these three projects, I contribute to our community to effectively detect type and memory safety violations.

As an extension to the ongoing Coconut (COde COnstructing User Tool) project at McMaster University, we present a Scala library for constructing type-safe domain-specific languages that uses Coconut’s hypergraph-based representation of code (code graphs) as the intermediate representation. Our library automatically produces strongly typed, deeply embedded DSLs given only a minimal specification of the DSL’s value types and primitives. We make extensive use of path-dependent types and implicit argument lookup to construct a type-safe interface on-the-fly, rather than requiring DSL designers to explicitly create a type-safe interface. In this thesis we present our library and demonstrate its utility as both a general-purpose DSL framework and as a suitable platform for continued research on the Coconut project. By giving practical examples of the library in use, we demonstrate both its general utility, and the striking swiftness with which new DSLs may be constructed, especially compared to the previously laborious Haskell DSLs of Coconut. / Thesis / Master of Science (MSc)

The increasing commoditization of computers in modern society has exceeded the pace of associated developments in reliability. Although theoretical computer science has advanced greatly in the last thirty years, many of the best techniques have yet to find their way into embedded computers, and their failure can have a great potential for disrupting society. This dissertation presents some approaches to improve computer reliability using software and hardware techniques, and makes the following claims for novelty: innovative development of a toolchain and libraries to support extraction from dependent type checking in a theorem prover; conceptual design and deployment in reconfigurable hardware; an extension of static type-safety to hardware description language and FPGA level; elimination of legacy C code from the target and toolchain; a novel hardware error detection scheme is described and compared with conventional triple modular redundancy. The elimination of any user control of memory management promotes robustness against buffer overruns, and consequently prevents vulnerability to common Trojan techniques. The methodology identifies type punning as a key weakness of commonly encountered embedded languages such as C, in particular the extreme difficulty of determining if an array access is in bounds, or if dynamic memory has been properly allocated and released. A method of eliminating dependence on type-unsafe libraries is presented, in conjunction with code that has optionally been proved correct according to user-defined criteria. An appropriately defined subset of OCaml is chosen with support for the Coq theorem prover in mind, and then evaluated with a custom backend that supports behavioural Verilog, as well as a fixed execution unit and associated control store. Results are presented for this alternative platform for reliable embedded systems development that may be used in future industrial flows. To provide assurance of correct operation, the proven software needs to be executed in an environment where errors are checked and corrected in conjunction with appropriate exception processing in the event of an uncorrectable error. Therefore, the present author’s previously published error detection scheme based on dual-rail logic and self-checking checkers is further developed and compared with traditional N-modular redundancy.

Computation with large-scale heterogeneous data typically requires universal traversal to search for all occurrences of a substructure that matches a possibly complex search pattern, whose context may be different in different places within the data. Both aspects cause difficulty for existing general-purpose programming languages, because these languages are designed for homogeneous data and have problems typing the different substructures in heterogeneous data, and the complex patterns to match with the substructures. Programmers either have to hard-code the structures and search patterns, preventing programs from being reusable and scalable, or have to use low-level untyped programming or programming with special-purpose query languages, opening the door to type mismatches that cause a high risk of program correctness and security problems. This thesis invents the concept of pattern structures, and proposes a general solution to the above problems - a programming technique using pattern structures. In this solution, well-typed pattern structures are defined to represent complex search patterns, and pattern searching over heterogeneous data is programmed with pattern parameters, in a statically-typed language that supports first-class typing of structures and patterns. The resulting programs are statically-typed, highly reusable for different data structures and different patterns, and highly scalable in terms of the complexity of data structures and patterns. Adding new kinds of patterns for an application no longer requires changing the language in use or creating new ones, but is only a programming task. The thesis demonstrates the application of this approach to, and its advantages in, two important examples of computation with heterogeneous data, i.e., XML data processing and Java bytecode analysis. / Thesis (Ph.D, Computing) -- Queen's University, 2007-08-27 09:43:38.888

No description available.

Mathematical optimization has many applications in operations research, image processing, and machine learning, demanding not only computational efficiency but also convenience and correctness in constructing complex models. In this work, we introduce HashedExpression, an open-source algebraic modeling lan- guage (AML) that allows users to express unconstrained, box-constrained, and scalar-expressions-constrained optimization problems, aimed at embeddability, type-safety, and high-performance through symbolic transformation and code generation. Written in Haskell, a statically-typed, purely functional program- ming language, HashedExpression places a great emphasis on modeling correct- ness by providing users with a type-safe, correct-by-construction interface that uses Haskell type-level programming to express constraints on correctness which the compiler uses to flag many modelling errors as type errors (at compile time). We show how type-safety can be added in steps, first matching expressions’ shape and then associated physical units. The library implements symbolic ex- pressions with a hashed indexing scheme to implement common subexpression elimination (CSE). It abstracts away details of the underlying lookup table via monadic type class instances. We explain how using symbolic expressions with CSE enables performance-enhance transformations and automatic computation of derivatives without the issue of “expression swelling”. For high-performance purposes, we generate low-level C/C++ code for symbolic expressions and pro- vide bindings to open-source optimization solvers such as Ipopt or L-BFGS-B. We explain how this architecture lays the groundwork for future work on par- allelization including SIMDization and targetting multi-core CPUs and GPUs, and other hardware acceleration. / Thesis / Master of Science (MSc)

Microfrontend applications are composed of multiple smaller frontend applications, which are integrated at run-time. As with microservices, microfrontends can be updated in production at any time. There are no technological restrictions for releasing API-breaking updates. Therefore it is difficult to trust microfrontend applications to perform reliably in run-time and to introduce API-breaking updates without the risk of breaking consumers. This thesis presents Plutt, a tool that provides automatic guarantees for safely consuming microfrontends, by ensuring that updates in run-time are compatible. By using Plutt, consumers can be confident that a provided microfrontend will per- form the same during production as in development. Likewise, microfrontend providers can release updates without being concerned about how it will affect consumers. Moreover, a comprehensive survey about microfrontends is presented, where five industry experts are interviewed. Aspects that are not found in existing literature are discovered, which contributes to a broader knowledge base that helps future microfrontend research. / Mikrofrontend-applikationer är sammansatta av flera mindre frontend-applikationer som integreras under exekvering. Precis som med mikrotjänster, kan mikrofrontends bytas ut i produktion när som helst. Det saknas teknologiska restriktioner för att publicera API-brytande uppdateringar. Därför är det svårt att lita på att en mikrofrontend-applikation beter sig tillförlitligt under exekvering samt att introducera API-brytande uppdateringar utan att riskera att förstöra konsumenter. Det här examensarbetet presenterar Plutt, ett verktyg som erbjuder automatiska garantier för att säkert konsumera mikrofrontends genom att säkerställa att uppdateringar som introduceras i körtid är kompatibla. Genom att använda Plutt, kan konsumenter vara trygga i vetskapen att en försedd mikrofrontend presterar likadant under produktion som i utveckling. Samtidigt kan utvecklare som förser mikrofrontends släppa uppdateringar utan att bekymra sig över hur det påverkar konsumenter. Utöver Plutt, presenteras en grundlig kartläggning över mikrofrontends, där fem experter från industrin är intervjuade. Aspekter som inte hittas i existerande litteratur är upptäckta, vilket kunskapsbas och framtida forskning om mikrofrontends.

<p>This thesis gives a partial answer to the question: “Can type systems detect modeling errors in scientific computing, particularly for inverse problems derived from physical models?” by considering, in detail, the major aspects of inverse problems in Magnetic Resonance Imaging (MRI). We define a type-system that can capture all correctness properties for MRI inverse problems, including many properties that are not captured with current type-systems, e.g., frames of reference. We implemented a type-system in the Haskell language that can capture the errors arising in translating a mathe- matical model into a linear or nonlinear system, or alternatively into an objective function. Most models are (or can be approximated by) linear transformations, and we demonstrate the feasibility of capturing their correctness at the type level using what is arguably the most difficult case, the (discrete) Fourier transformation (DFT). By this, we mean that we are able to catch, at compile time, all known errors in ap- plying the DFT. The first part of this thesis describes the Haskell implementation of vector size, physical units, frame of reference, and so on required in the mathemat- ical modelling of inverse problems without regularization. To practically solve most inverse problems, especially those including noisy data or ill-conditioned systems, one must use regularization. The second part of this thesis addresses the question of defining new regularizers and identifying existing regularizers the correctness of which (in our estimation) can be formally verified at the type level. We describe such Bayesian regularization schemes based on probability theory, and describe a novel simple regularizer of this type. We leave as future work the formalization of such regularizers.</p> / Master of Science (MSc)

This thesis aims to provide recommendations for interfacing two memory-safe programming languages, Rust and SPARK. The comparison of Rust and C/C++, as well as SPARK and C/C++, has been thoroughly researched. However, this level of investigation hasn’t been as extensive between memory-safe languages. SPARK is a subset of Ada, a programming language with a long track record in safety-critical applications. Rust is a multi-paradigm language that has gained popularity since its emergence roughly a decade ago. Both languages implement ownership systems and type safety, which are instrumental in developing safe and reliable software. Memory-safety bugs in code written in C/C++ account for about 70 % of major vulnerabilities in the industry, as reported by organizations such as Microsoft, Apple, and Google. While tools to avoid memory errors exist, code cannot be made safe retroactively, which creates a need for languages designed with safety in mind, such as Rust and SPARK. Combining those two languages is a very promising path for low-level and systems programming and safety-critical applications (automotive, avionics, medical etc.). This thesis identifies best practices for safe bindings between Rust and SPARK, focusing on ensuring memory safety, type safety, and ownership, and then analyzes how to maintain or transfer those properties. The thesis provides clear recommendations based on control study programs and a real-world example using BBQueue, a circular buffer library suitable for embedded systems implemented in both languages. The identified best practices can be used for safe bindings and automated tools/code generation. This thesis fills a gap in existing research, primarily focusing on combining safe and unsafe languages. It provides a valuable contribution to software security and safety-critical systems. / Denna avhandling syftar till att ge rekommendationer för att koppla samman två minnessäkra programmeringsspråk, Rust och SPARK. Sådana kombinationer har redan studerats utförligt mellan Rust/SPARK och de osäkra språken C/C++, men det finns relativt lite information och forskning angående minnessäkra språk. SPARK är en delmängd av Ada, ett språk som har använts i decenier i säkerhetskritiska applikationer. Rust är ett multiparadigmatiskt språk som har blivit populärt sedan dess skapande för ungefär ett decennium sedan. Båda språken implementerar ägarskapssystem och typsäkerhet, vilka är avgörande för att utveckla säkra och tillförlitliga programvaror. Minnesfel i C/C++ står för cirka 70 procent av de stora sårbarheterna i branschen, som rapporterats av organisationer såsom Microsoft, Apple och Google. Även om det finns verktyg för att undvika minnesfel kan koden inte göras säker retroaktivt, vilket skapar ett behov av språk som är designade med säkerhet i åtanke. Att kombinera Rust och SPARK är en mycket lovande väg för systemprogrammering, låg nivå och säkerhetskritiska applikationer (bilindustri, flygavionik, medicinskt etc). Denna avhandling identifierar bästa praxis för säkra bindningar mellan Rust och SPARK, med fokus på att säkerställa minnessäkerhet, typsäkerhet och ägarskap, och analyserar sedan hur man kan behålla eller överföra dessa egenskaper. Avhandlingen ger klara rekommendationer baserade på kontrollstudieprogram och ett exempel med hjälp av BBQueue, ett cirkulärt buffertbibliotek som används i inbyggda system. Dessa resulat kan användas för att skapa säkra bindningar, manuelt eller med ett automatiserat verktyg. Denna avhandling fyller en lucka i befintlig forskning, som främst fokuserar på att kombinera säkra och osäkra språk. Den bidrar värdefullt till programvarusäkerhet och säkerhetskritiska system.