Calvin Cheuk Wang Ko September 1996 Computer Science Execution Monitoring of Security-Critical Programs in a Distributed System: A Specification-Based Approach Major Professor: Karl N. Levitt Abstract: Many security problems are directly or indirectly related to vulnerabilities in security-critical programs. Intruders exploit vulnerabilities in these programs to gain unauthorized access to a system. We present a new approach to intrusion detection that can detect exploitations of vulnerabilities in these programs. The approach is specification-based because it is concerned with writing security specifications that capture the desirable behavior of programs with respect to security. Any behavior inconsistent with the specifications indicates a security threat to the system. We depend on audit logs to capture the behavior of a program, and use the specifications as oracles against which the behavior is checked. A security specification describes the sequence of operations a program should perform during execution, and is called a trace policy. A novel type of grammar, called parallel environment grammar (PE-grammar) is used to specify trace policies. The alphabets are operations, and an execution trace of a program is valid if it is a sentence specified by the grammar. The language is able to specify many different kinds of program behavior. In addition, a PE-grammar serves as a design specification of a top-down parallel parser (the detection engine) that recognizes the language (valid operation sequences) specified by the grammar. We built a prototype real-time monitoring system in Unix, and developed trace policies for approximately 15 privileged programs in Unix; in principle, all Unix privileged programs can be specified using the PE-grammar. The system is able to detect known attacks on these programs and has the potential to detect new attacks. Also it can detect exploitations of race-conditions in privileged programs and security violations caused by improper synchronization in distributed programs.