Design and Analysis of Real-Time Embedded Software Systems (Dissertation Topic)
Publications: AEFL08, DISSERTATION PROPOSAL, EAL07, ELSS07, ESSL06
Advisors: Prof. Insup Lee and Prof. Oleg Sokolsky
Organization: University of Pennsylvania, Philadelphia, USA

Objectives: To develop framework and tool for modular, component-based, design and analysis of real-time embedded systems. This framework must support software components with communication dependencies between them, and must also allow for runtime modifications to these components.

Achievements: We have developed a framework for abstraction of software components into interfaces. An interface captures component information necessary for design and analysis, and at the same time hides away internal complexities. This technique enables separation of concerns among different components, and hence helps in system integration. It also provides support for analysis of non-functional system properties such as schedulability. The framework can efficiently handle runtime modifications to components, and also supports components with communication dependencies between them. Currently, we are developing a JAVA based tool that implements this framework.

Virtual Cluster-based Scheduling in Multiprocessors
Publications: SEL08(to appear in ECRTS 2008)
Advisor: Prof. Insup Lee
Organization: University of Pennsylvania, Philadelphia, USA

Objectives: To develop techniques for scheduling real-time workload on virtual processor clusters in multiprocessor platforms. These techniques must support different intra- and inter-cluster schedulers, and also allow general task-cluster mappings.

Achievements: Considering a two-level hierarchical scheduling framework, we have developed cluster interfaces and used them in inter-cluster scheduling. Each cluster interface abstracts intra-cluster resource demand using minimum processor utilization. This technique separates intra- and inter-cluster scheduling, thereby allowing use of different schedulers, and does not enforce any restriction on task-cluster mappings.

Design of ARINC-653 Software Partitions in Avionics Real-Time Operating System
Mentor: Steve Vestal
Organization: Honeywell Aerospace Inc.- Advanced Technology, Minneapolis, USA

Objectives: Our primary goal in this summer project was to develop a technique for design of ARINC-653 partitions (software components) in avionics real-time operating systems. Partitions are developed by independent third party vendors, and communicate with each other forming a distributed system. Hence, the technique we develop must separate concerns between partitions, and must also consider the effects of communication dependencies. In addition, safety critical nature of the application domain demands satisfaction of hard real-time deadlines, and requires the system to meet stringent certification norms.

Achievements: We adapted the above described component abstraction technique to develop interfaces for ARINC-653 partitions. This also involved exploiting ARINC-specific properties in order to improve resource efficiency of partition interfaces. Third party partition vendors can now specify interfaces capturing necessary information from their partitions, and system integration can then be achieved by scheduling these interfaces on hardware platforms. Prototypes showed that interfaces are highly efficient and well suited for abstracting partitions. Analytical correctness guarantees of the technique ensure satisfaction of hard real-time deadlines, and also assist in system certification.

Quantitative Simulation for Detecting Similarities in Computer Viruses
Publications: EKL05
Advisors: Prof. Sampath Kannan, Prof. Insup Lee, and Prof. Oleg Sokolsky
Organization: University of Pennsylvania, Philadelphia, USA

Objectives: To develop a technique for classifying computer virus programs based on their structural and semantic similarities. This technique should be resilient to various obfuscation (malicious code hiding) techniques that are frequently used by virus developers.

Achievements: We worked on a technique called quantitative simulation (qsim) that uses control and data flow information from computer programs. Approach is similar to the well-known bi-simulation technique used in software testing. qsim compares states of two computer programs based on the structure of subsequent execution paths and the semantic meaning of states in those paths. We experimentally evaluated qsim in order to fine tune its parameters for various known obfuscation techniques.

Steering (Runtime Control) of Software for Error Prevention
Publications: EKS05, SESL04
Advisors: Prof. Sampath Kannan, Prof. Insup Lee, and Prof. Oleg Sokolsky
Organization: University of Pennsylvania, Philadelphia, USA

Objectives: To extend existing runtime software verification techniques so that they support runtime error correction as well. The technique must detect and correct errors before they occur in an execution. Furthermore, the technique must minimally interfere with system execution when no errors are detected.

Achievements: We developed a runtime error correction technique by adapting discrete control theory to runtime software verification. This technique uses look-ahead to predict erroneous system execution paths, and then prevents those paths using control actions. System executes without any interference from the runtime controller, until control actions need to be executed. In recent extensions to this technique, we also consider error correction in probabilistic system models. This probabilistic approach not only minimizes errors, but also maximizes the expected system functionality.

Vehicle Routing Algorithms for Postal Delivery Networks
Mentor: Prof. Subramani Arunkumar
Organization: Indian Institute of Technology, Bombay, India

Objectives: To develop vehicle routing algorithms in order to minimize the operational cost of postal delivery networks in the city of Bombay, India. These algorithms must consider various operational constraints such as vehicular traffic on roads affecting travel time, maximum permissible duration of trips, and synchronization with train and flight timings.

Achievements: We developed and implemented a vehicle routing algorithm that significantly reduced operational cost of the postal delivery network. It took into consideration operational constraints listed above, and minimized not only daily recurring costs like fuel, but also reduced capital investments like number of vehicles and personnel.