Regular slot: Tuesday (except for the first Tuesday each month), 16:15-17:15h, in room BC 355 (Tresor Conference and Coffee Room)
In real-time critical applications (e.g. automotive, aerospace), it is necessary to guarantee that the body of control loops execute within certain time bounds. The problem of finding the worst case execution time of a program, or at least bounding it reasonably tightly, is hard for two reasons: (1), current architectures are very complex, with caches, shared components and pipelines, and using methods valid 25 years ago (take the worst-case time of each instruction and sum) would lead to gross overapproximation; (2), even if a path in the code is syntactically feasible, it is not necessarily so if taking into account the semantics of the program (e.g. two blocks of code apply to two disjoint modes of operation of the system and cannot be executed both in a single iteration).
One alluring idea is to use bounded model-checking by SMT-solving to determine the worst-case execution time (which takes care of (2) and even (1)). Doing so naively is however prohibitively expensive; we have experimental results and theoretical explanations for this. We provide a solution to this problem, based on local abstractions.
I will present an overview of results that emerged from type theoretic techniques. A particular attention will be given to the reducibility method in logic. Further, the role of classical types will be presented in the framework of delimited continuations. Finally, the role of types will be discussed in security control issues of linked documents and linked data.
Word level compilers and linkers apply transformations at the word level to generate smaller and faster programs. Several techniques at the Boolean and circuit levels effectively reduce the complexity and the size of the program and make it amenable to decision procedures such as satisfiability solvers. These techniques miss many opportunities of optimizations that exist at the word level. Transformations such as word based compositional minimization, and word based abstractions are not even possible at the Boolean or circuit levels. In this talk we consider several techniques for program analysis including word level transformation based analysis.