Sleep Convention Logic (SCL) is an emerging ultra-low power Quasi-Delay Insensitive (QDI) asynchronous design paradigm with enormous potential for industrial applications. Design validation is a critical concern before commercialization. Unlike other QDI paradigms, such as NULL Convention Logic (NCL) and Pre-Charge Half Buffers (PCHB), there exists no formal verification methods for SCL. In this thesis, a unified formal verification scheme for combinational as well as sequential SCL circuits is proposed based on equivalence checking, which verifies both safety and liveness. The method is demonstrated using several multipliers, MACs, and ISCAS benchmarks.

Různé typy logik se často používají jako prostředky pro formální specifikaci systémů. Slabá monadická logika druhého řádu s k následníky (WSkS) je jednou z nich a byť má poměrně velkou vyjadřovací sílu, stále je rozhodnutelná. Ačkoliv složitost testování splnitelnosti WSkS formule není ani ve třídě ELEMENTARY, tak existují přístupy založené na deterministických automatech, implementované např. v nástroji MONA, které efektně řeší omezenou třídu praktických příkladů, nicméně nefungují pro jiné. Tato práce rozšiřuje třídu prakticky řešitelných příkladů, a to tak, že využívá nedávno vyvinutých technik pro efektní manipulaci s nedeterministickými automaty (jako je například testování universality jazyka pomocí přístupu založeného na antichainech) a navrhuje novou rozhodovací proceduru pro WSkS využívající právě nedeterministické automaty. Procedura je implementována a ve srovnání s nástrojem MONA dosahuje v některých případech řádově lepších výsledků.

This dissertation addresses the top two “most critical web-application security risks” by combining two high-level contributions. The first high-level contribution introduces and evaluates collaborative authentication, or coauthentication, a single-factor technique in which multiple registered devices work together to authenticate a user. Coauthentication provides security benefits similar to those of multi-factor techniques, such as mitigating theft of any one authentication secret, without some of the inconveniences of multi-factor techniques, such as having to enter passwords or biometrics. Coauthentication provides additional security benefits, including: preventing phishing, replay, and man-in-the-middle attacks; basing authentications on high-entropy secrets that can be generated and updated automatically; and availability protections against, for example, device misplacement and denial-of-service attacks. Coauthentication is amenable to many applications, including m-out-of-n, continuous, group, shared-device, and anonymous authentications. The principal security properties of coauthentication have been formally verified in ProVerif, and implementations have performed efficiently compared to password-based authentication. The second high-level contribution defines a class of SQL-injection attacks that are based on injecting identifiers, such as table and column names, into SQL statements. An automated analysis of GitHub shows that 15.7% of 120,412 posted Java source files contain code vulnerable to SQL-Identifier Injection Attacks (SQL-IDIAs). We have manually verified that some of the 18,939 Java files identified during the automated analysis are indeed vulnerable to SQL-IDIAs, including deployed Electronic Medical Record software for which SQL-IDIAs enable discovery of confidential patient information. Although prepared statements are the standard defense against SQL injection attacks, existing prepared-statement APIs do not protect against SQL-IDIAs. This dissertation therefore proposes and evaluates an extended prepared-statement API to protect against SQL-IDIAs.

The current standard for remote identification of unmanned aircraft does not contain anyform of security considerations, opening up possibilities for impersonation attacks. Thenewly proposed Drone Remote Identification Protocol aims to change this. To fully ensurethat the protocol is secure before real world implementation, we conduct a formal verification using the Tamarin Prover tool, with the goal of detecting possible vulnerabilities. Theunderlying technologies of the protocol are studied and important aspects are identified.The main contribution of this thesis is the formal verification of session key secrecy andmessage authenticity within the proposed protocol. Certain aspects of protocol securityare still missing from the scripts, but the protocol is deemed secure to the extent of themodel. Many features of both the protocol and Tamarin Prover are presented in detail,serving as a potential base for the continued work toward a complete formal verificationof the protocol in the future.

Today's vehicles are increasingly controlled by embedded computer systems. Such systems are of safety-critical nature, where an error in the computation could have dire consequences. A common way to ensure that software works is testing, but as the complexity of these systems grows larger it gets harder to ensure enough coverage in the tests. Another way to ensure that software fulfills its requirements is formal verification, where properties of the code are proven mathematically to hold under certain conditions. Formal verification gives a higher level of confidence in the correctness of code than testing alone, but it is not as widely used within the industry. This project has examined whether current state-of-the-art tools for formal verification are ready to be used to verify real-life safety-critical code. To answer this, a case study on a module running in Scania's vehicles was performed. Several of the requirements were successfully verified. The thesis also identifies for what type of code and requirements this is possible, and describes a process for how it can be done. / Idag kontrolleras fordon allt mer av inbyggda datorsystem. Sådana system är säkerhetskritiska, där ett fel kan ha ödesdigra konsekvenser. Ett vanligt sätt att försäkra sig om att mjukvaran fungerar är testning, men när komplexiteten av dessa system växer blir det allt svårare att försäkra sig om att testen har tillräcklig täckning. Ett annat sätt att försäkra sig om att mjukvaran uppfyller dess krav är formell verifiering, där egenskaper hos koden bevisas matematiskt att hålla under vissa villkor. Formell verifiering ger ett högre förtroende för kods korrekthet än vad enbart testning skulle göra, men används ännu inte i lika stor utsträckning inom industrin. Detta projekt har undersökt huruvida moderna verktyg för formell verifiering är mogna att användas för att verifiera riktig säkerhetskritisk kod. För att svara på detta har en fallstudie av en modul i Scanias fordon genomförts. Flera av dess krav lyckades verifieras. Rapporten identifierar också för vilka typer av kod och krav detta är möjligt, och beskriver en process för hur det kan utföras.

One of the issues when attempting to verify security properties of a protocol is how to model the protocol. We introduce a method for verifying event freshness in tools which use the applied π-calculus and are able to verify secrecy. Event freshness can be used to prove that a protocol never generates the same key twice. In this work we encode state in the applied π-calculus and perform bounded verification of freshness for MiniDC by using the ProVerif tool. MiniDC is a trivial protocol that for each iteration of a loop generates a unique key and outputs it to a private channel. When verifying freshness, the abstractions of ProVerif cause false attacks. We describe methods which can be used to avoid false attacks that appear when verifying freshness. We show how to avoid some false attacks introduced by private channels, state and protocols that disclose their secret. We conclude that the method used to verify freshness in MiniDCis impractical to use in more complicated protocols with state. / Ett av problemen som uppstår vid verifiering av säkerhetsprotokoll är hur protokoll ska modelleras. Vi introducerar en metod för att verifiera att skapde termer inte har använts förr. Denna metod kan användas i program som använder applicerad π-kalkyl som input och kan verifiera sekretess. I detta arbete visar vi hur protokoll med persistenta variabler kan modelleras i applicerad π-kalkyl. Vi verifierar även MiniDC för ett begränsat antal iterationer med hjälp av ProVerif. MiniDC är ett enkelt protokoll som för varje iteration av en loop skapar en nyckel och skickar den över en privat kanal. När man verifierar att skapade termer inte har använts förr så introducerar ProVerifs abstraktioner falska attacker. Vi beskriver metoder som kan användas för att undvika dessa falska attacker. Dessa metoder kan användas för falska attacker introducerade av privata kanaler, persistenta variabler eller protokoll som avslöjar sin krypteringsnyckel. Vår slutsats är att metoden som används för att verifiera MiniDC är opraktisk att använda i mer komplicerade protokoll med persistenta variabler.

In this report we present a graphical tool, Behavioral Analysis of Spacecraft Systems (BASS), that can be used by spacecraft designers to perform system-level behavioral analysis of small satellites. The domain-specific spacecraft meta-model is created in the visual modeling tool Generic Modeling Environment (GME) such that spacecraft designs created using the meta-model appear familiar to the spacecraft designers. Users can model scenarios that are to be verified for the design in BASS. The graphical models are assigned formal semantics facilitating the creation of formally verifiable spacecraft models. The C++ application that translates the modeling objects to equivalent mathematical representation of interest is called BASS Interpreter and is bound to the meta-model. BASS Interpreter that generates Communicating Sequential Processes (CSP) semantics for the visual spacecraft models is supported in the current work. The model-checker for CSP called Failures Divergences and Refinement (FDR) is run to explore the state-space of the spacecraft process model to comment on the design. We demonstrate the feasibilty and advantage of incorporating BASS into initial design phases of small satellite development by successfully verifying the design of Tomographic Remote Observer of Ionospheric Disturbances (TOROID).

This work focuses on the usage of dominators in circuit graphs in order to reduce the complexity of synthesis and verification tasks. One of the contributions of this thesis is a new algorithm for computing multiple-vertex dominators in circuit graphs. Previous algorithms, based on single-vertex dominators suffer from their rare appearance in many circuits. The presented approach searches efficiently for multiple-vertex dominators in circuit graphs. It finds dominator relations, where algorithms for computing single-vertex dominators fail. Another contribution of this thesis is the application of dominators for combinational equivalence checking based on the arithmetic transform. Previous algorithms rely on representations providing an explicit or implicit disjoint function cover, which is usually excessive in memory requirements. The new algorithm allows a partitioned evaluation of the arithmetic transform directly on the circuit graph using dominator relations. The results show that the algorithm brings significant improvements in memory consumption for many benchmarks. Proper cuts are used in many areas of VLSI. They provide cut points, where a given problem can be split into two disjoint sub-problems. The algorithm proposed in this thesis efficiently detects proper cuts in a circuit graph and is based on a novel concept of a reduced dominator tree. The runtime of the algorithm is less than 0.4 seconds for the largest benchmark circuit. The final contribution of this thesis is the application of the proper cut algorithm as a structural method to decompose a Boolean function, represented by a circuit graph. In combination with a functional approach, it outperforms previous methods, which rely on functional decomposition only.

Formal verification methods have been shown to be very effective in finding corner-case bugs and ensuring the safety of embedded software systems. The use of formal verification requires a specification, which is typically a high-level mathematical model that defines the correct behavior of the system to be verified. However, embedded software requirements are typically described in natural language. Transforming these requirements into formal specifications is currently a big gap. While there is some work in this area, we proposed solutions to address this gap in the context of refinement-based verification, a class of formal methods that have shown to be effective for embedded object code verification. The proposed approach also addresses both functional and timing requirements and has been demonstrated in the context of safety requirements for software control of infusion pumps. The next step in the verification process is to develop the refinement map, which is a mapping function that can relate an implementation state (in this context, the state of the object code program to be verified) with the specification state. Actually, constructing refinement maps often requires deep understanding and intuitions about the specification and implementation, it is shown very difficult to construct refinement maps manually. To go over this obstacle, the construction of refinement maps should be automated. As a first step toward the automation process, we manually developed refinement maps for various safety properties concerning the software control operation of infusion pumps. In addition, we identified possible generic templates for the construction of refinement maps. Recently, synthesizing procedures of refinement maps for functional and timing specifications are proposed. The proposed work develops a process that significantly increases the automation in the generation of these refinement maps. The refinement maps can then be used for refinement-based verification. This automation procedure has been successfully applied on the transformed safety requirements in the first part of our work. This approach is based on the identified generic refinement map templates which can be increased in the future as the application required.

Software systems are frequently designed using abstractions that make software verification tractable. Specifically, by choosing meaningful, formal abstractions for interfaces and then designing according to those interfaces, one can verify entire systems according to behavioral predicates. While impractical for systems in general, framework-based software architectures are a type of system for which formal analysis can be beneficial and practical over the life of the system. We present a method to formally analyze behavioral properties of framework-based software with higher-order logic and then demonstrate its utility for a significant, modern system.