Finite state machines and pushdown systems are frequently used in model based testing. In such testing, the system under test is abstractly modeled as a finite state machine having a finite set of states and a labeled transition relation between the states. A pushdown system, additionally, has an unbounded stack. Test inputs are then generated by enumerating a set of sequences of transitions labels from the model. There has been a lot of research that focussed on generation of test input sequences satisfying various coverage criteria. In this paper, we consider the problem of generating a set of test input sequences that satisfy certain coverage criteria-cover all transition labels or cover all length-n transition label sequences at least once-while minimizing the sum of the length of the sequences in the set. We show that these optimal test input generation problems can be reduced to integer linear programming (ILP) problems. We also prove that our optimal test input generation problems are NP-Complete. We report our experimental results on a prototype implementation for finite states machines.

Web applications routinely handle sensitive data, and many people rely on them to support various daily activities, so errors can have severe and broad-reaching consequences. Unlike most desktop applications, many web applications are written in scripting languages, such as PHP. The dynamic features commonly supported by these languages significantly inhibit static analysis and existing static analysis of these languages can fail to produce meaningful results on realworld web applications.

It is notoriously difficult to program a solid web application. Besides addressing web interactions, state maintenance, and whimsical user navigation behaviors, programmers must also avoid a minefield of security vulnerabilities. The problem is twofold. First, we lack a clear understanding of the new computation model underlying web applications. Second, we lack proper abstractions for hiding common and subtle coding details that are orthogonal to the business functionalities of specific web applications.

It is well recognized that JavaScript can be exploited to launch browser-based security attacks. We propose to battle such attacks using program instrumentation. Untrusted JavaScript code goes through a rewriting process which identifies relevant operations, modifies questionable behaviors, and prompts the user (a web page viewer) for decisions on how to proceed when appropriate. Our solution is parametric with respect to the security policy-the policy is implemented separately from the rewriting, and the same rewriting process is carried out regardless of which policy is in use. Be-sides providing a rigorous account of the correctness of our solution, we also discuss practical issues including policy management and prototype experiments. A useful by-product of our work is an operational semantics of a core subset of JavaScript, where code embedded in (HTML) documents may generate further document pieces (with new code embedded) at runtime, yielding a form of self-modifying code.

Concurrency, as a useful feature of many modern programming languages and systems, is generally hard to reason about. Although existing work has explored the verification of concurrent programs using high-level languages and calculi, the verification of concurrent assembly code remains an open problem, largely due to the lack of abstraction at a low-level. Nevertheless, it is sometimes necessary to reason about assembly code or machine executables so as to achieve higher assurance.In this paper, we propose a logic-based "type" system for the static verification of concurrent assembly programs, applying the "invariance proof" technique for verifying general safety properties and the "assume-guarantee" paradigm for decomposition. In particular, we introduce a notion of "local guarantee" for the thread-modular verification in a non-preemptive setting.Our system is fully mechanized. Its soundness has been verified using the Coq proof assistant. A safety proof of a program is semi-automatically constructed with help of Coq, allowing the verification of even undecidable safety properties. We demonstrate the usage of our system using three examples, addressing mutual exclusion, deadlock freedom, and partial correctness respectively.

We present a formalization of the implementation of generics in the .NET Common Language Runtime (CLR), focusing on two novel aspectsof the implementation: mixed specialization and sharing, and efficient support for run-time types. Some crucial constructs used in the implementation are dictionaries and run-time type representations. We formalize these aspects type-theoretically in a way that corresponds in spirit to the implementation techniques used in practice. Both the techniques and the formalization also help us understand the range of possible implementation techniques for other languages, e.g., ML, especially when additional source language constructs such as run-time types are supported. A useful by-product of this study is a type system for a subset of the polymorphic IL proposed for the .NET CLR.