Power and energy optimizations include both reducing total energy consumption and improving time-dependent power behavior. Fine-grained program power behavior is useful in evaluating power optimizations and observing power optimization opportunities. In this paper, we present a physical measurement-based infrastructure for program time-dependent power behavior characterization and optimization evaluation. This infrastructure does basic block profiling, a SimPoint-like phase classification, and precise physical measurement for selected representative program execution slices. Our phase classification method uses infrequently executed basic blocks to demarcate intervals and uses a user-specified interval size to control the length of the resulting intervals. This partitioning method incurs low instrumentation overhead for dynamic identification of simpoints during program execution. This physical measurement infrastructure enables precise power measurement for any program execution. This infrastructure is built on our Camino compiler, which supports static instrumentation on various levels. This infrastructure can be used to characterize detailed program power behavior, as well as evaluate compiler and architecture level power and energy optimizations. We validate the feasibility of this phase classification method in power behavior characterization through the physical measurement of 10 SPEC CPU2000 integer benchmarks on a Pentium 4 machine. Experimental results show that our method can also nd representative slices for power behavior estimation, and the physical measurement with negligible instrumentation overhead enables us to estimate detailed time-dependent program power behavior.

Many modern scientific computations require the manipulation of numbers that are too big to fit in a word of memory. These computations create the need to develop compound representations for integers, called bignums, and algorithms to support arbitrary precision arithmetic operations. One of the fundamental algorithms that must be implemented is bignum multiplication. The most popular and best known implementations of bignum multiplication use as their base case algorithm the classical algorithm described by Knuth. This algorithm is modeled on the multiplication algorithm taught in grade school and is optimized to eliminate redundant memory allocation. Under certain conditions, however, Knuth's classical algorithm suffers from limited degree of locality of reference. In this article, we outline a new base case bignum multiplication algorithm that carries out the computation with a higher degree of locality of reference when the size of the multiplier is less than two thirds the size of the multiplicand.

As a result of terrorist attacks, national security has become more worried with the possibility of future occurrences and what actions can be taken to help prevent future occurrences. The U.S. Department of Homeland Security has requested proposals that provide a security tool to assist the U.S. Customs and Border Protection (CBP) to supervise shipments that enter into the United States. Cargo City will help protect the nation's water supply by tracking dry and liquid bulk shipments from origin to final destination.

At this time only 10% of shipments that enter the United States are randomly inspected as they cross the U.S. border. As an outcome of tracking bulk shipments from origin to final destination the chance of an improper shipment, which could be used to pollute the nation's water supply, slipping past the border is drastically reduced.

These improper shipments, whether they be intentional contaminates or toxic solvents, cause destruction to the water supply as well as the creatures that depend on that water supply. Any discarding of toxic solvents, from misuse or criminal intent, causes damage which is indistinguishable from that caused by those individuals or factions who have the objective of causing harm to the nation's water supply.

Cargo City is a centralized, Internet-based database that will serve as a security instrument to assist in the tracking of tankers and identification of the drivers. When a tanker is loaded at its origin a manifest, driver and tanker information have already been transmitted to Cargo City and approved by the U.S. Customs database (ACE). After the tanker is loaded, all openings are sealed with disposable barcodes. Cargo City communicates with the shipper, the receiver and ACE. Cargo City contains a database with the manifest, the tanker being used and the driver(s) information.

The spiral process model was chosen for this project as a result of the need to re-work and refine some of the coding already in existence for Cargo City. The languages used for this project are Java, HTML/JavaScript, JSP, JDBC/ODBC, Microsoft Access(R) for the database, and Apache Tomcat.

Databases are everywhere. Whether it is commercial or scientific, a database is used. Therefore, it is essential that these database applications work correctly. Testing these database applications correctly and effectively is a challenge. AGENDA (A (test) GENerator for Database Applications) was designed to aid in testing database applications. In addition to the tools that AGENDA currently has, three additional tools were made to enhance testing and feedback. They are the log analyzer, attribute analyzer, and query coverage. The log analyzer finds relevant entries in log file produced by DBMS, lexically analyzes them using a grammar written in JavaCC, and stores some of the data in a database table. When the log entry represents an executed SQL statement, this statement is recorded. The attribute analyzer parses SQL statements. A SQL grammar for JavaCC was modified, adding code to determine which attributes are read and written in each SQL statement. A new test coverage criterion, query coverage, is defined. Query coverage checks whether queries that the tester thinks should be executed actually are executed. Similar to log analyzer, JavaCC was used to implement this. It is implemented by pattern matching executed queries against patterns representing abstract queries (including host variables) identified by the tester.

To facilitate managing access control in a system, access control policies are increasingly written in specification languages such as XACML. A dedicated software component called a Policy Decision Point (PDP) interprets the specified policies, receives access requests, and returns responses to inform whether access should be permitted or denied. To increase confidence in the correctness of specified policies, policy developers can conduct policy testing by supplying typical test inputs (requests) to the PDP and subsequently checking test outputs (responses) against expected ones. Unfortunately, manual testing is tedious and few tools exist for automated testing of XACML policies.

In this paper, we present our work toward a framework for systematic testing of access control policies. The framework includes components for policy coverage definition and measurement, request generation, request evaluation, request set minimization, policy property inference, and mutation testing. This framework allows us to evaluate various criteria for test generation and selection, investigate mutation operators, and determine a relationship between structural coverage and fault-detection capability. We have implemented the framework and applied it to various XACML policies. Our experimental results offer valuable insights into choosing mutation operators in mutation testing and choosing coverage criteria in test generation and selection.

Creating effective test cases is a difficult problem, especially for web applications. To comprehensively test a web application's functionality, test cases must test complex application state dependencies and concurrent user interactions. Rather than creating test cases manually or from a static model, field data provides an inexpensive alternative to creating such sophisticated test cases. An existing approach to using field data in testing web applications is user-session-based testing. However, previous user-session-based testing approaches ignore state dependences from multi-user interactions. In this paper, we propose strategies for leveraging web application field data to automatically create test cases that test various levels of multi-user interaction and state dependencies. Results from our preliminary case study of a publicly deployed web application show that these test case creation mechanisms are a promising testing strategy for web applications.

Any time source code is analyzed, whether for maintenance or general code comprehension, identifiers play a key role. Their makeup, therefore, is very important. Each identifier can be thought of as constructed from individual words, where each word may be found in a natural language dictionary or might be an abbreviation, a programming language key word, a program-specific word, or just plain gibberish. A summary of the types of words found in the code can indicate, at a glance, how comprehensible the code will be.

The problem of determining the words that make up an identifier in the absence of explicit word divisions such as underscores and camel-casing is addressed. One approach considered is a greedy algorithm. However, greedy algorithms can be time and space inefficient, making them less desirable. One interesting alternative is an artificial neural network. Neural networks are fast and have been used for speech and vision recognition, as well as a host of other patter-recognition tasks. This paper describes both a greedy algorithm and an a neural network (using the C-implementation of the Fast Artificial Neural Network) that are used to split non-well separated identifiers.

Parallel changes are becoming increasingly prevalent in the development of large scale software system. To deepen the study on the relationship between parallel changes and faults, we have designed a tool to detect the direct semantic interference between parallel changes. In this paper, we describe an empirical study to evaluate this semantic interference detection tool. We first mine the change and version management repositories to find sample versions sets of different degree of parallel changes. On the basis of the analysis reports, we mine the change and version repositories to find out what faults were discovered subsequent to the analyzed versions. We will also determine the lapse and cost data for finding and fixing the faults associated with those samples. This approach provides a significant and low cost method for effectively evaluating the usefulness of software tools.

Software users inevitably have to send an error report to the software developer so that the developer can locate and fix bugs revealed in the field. Privacy-conscious users have been forced to either send sensitive data to the developer or send no error report at all---and potentially never have the bug fixed. Current debugging work suggests either performing the debugging process at the user site or collecting enough random data such that no individual user's information can be identified. Until now, users have not had a systematic way of evaluating the amount of sensitive information revealed by an error report. In this poster we demonstrate the challenges and propose an overall approach for viewing the information revealed by debugging feedback. Depending on the severity of the bug, the user can then decide whether the amount of information revealed is acceptable---and feel confident the developer will gain no sensitive information from the debugging feedback.

The continuous use of the web for daily operations by businesses, consumers, and the government has created a great demand for reliable web applications. One promising approach to testing the functionality of web applications leverages user-session data collected by web servers. User-session-based testing automatically generates test cases based on real user profiles. The key contribution of this paper is the application of concept analysis for clustering user sessions and a set of heuristics for test case selection. Existing incremental concept analysis algorithms are exploited to avoid collecting and maintaining large user-session data sets and thus to provide scalability. We have completely automated the process from user session collection and test suite reduction through test case replay. Our incremental test suite update algorithm coupled with our experimental study indicate that concept analysis provides a promising means for incrementally updating reduced test suites in response to newly captured user sessions with little loss in fault detection capability and program coverage.

The generation of efficient addressing code is a central problem in compiling for processors with restricted addressing modes, like Digital Signal Processors (DSPs). Offset Assignment (OA) is the problem of allocating scalar variables to memory, so as to minimize the need of addressing instructions. This problem is called Simple Offset Assignment (SOA) when a single address register is available, and General Offset Assignment (GOA), when more address registers are used. This poster shows how variables' liveness information can be used to dramatically reduce the addressing instructions required to access local variables on the program stack. Two techniques that make effective use of variable coalescing to solve SOA and GOA are described, namely Coalescing SOA (CSOA) and Coalescing GOA (CGOA). In addition, a thorough comparison between these algorithms and others described in the literature is presented. The experimental results, when compiling MediaBench benchmark programs with the LANCE compiler, reveal a very significant improvement of the proposed techniques over the other available solutions to the problem.

A deadlock occurs when two or more threads are involved in a cyclic wait for resources. Deadlocked threads cannot make further progress until they are resolved. The sooner a deadlock is detected, the earlier and perhaps easier it can get resolved. In this paper, we establish a model based on partially observable markov decision processes (POMDP) to solve the optimal policy for detecting Java deadlocks, and use some simulation studies to verify our model.

Software robustness and security are critical to dependable operations of computer systems. Robustness and security of software systems are governed by various temporal properties. Static verification has been shown to be effective in checking temporal properties. But manually specifying these properties is cumbersome and requires knowledge of the system and source code. Furthermore, many system-specific correctness properties that govern the robust and secure operation of software systems are often not documented by the developers. We design and implement a novel framework to effectively generate a large number of concrete interface robustness properties for static verification from a few generic, high-level user specified robustness rules for exception handling. These generic rules are free from any system or interface details, which are automatically mined from the source code. We report our experience of applying this framework to test robustness of POSIX-APIs in Redhat-9.0 open source packages. Security properties that dictate the ordering of certain system calls are usually inter-procedural unlike robustness properties. In this paper, we present our ongoing research that infers these properties directly from the program source code by applying statistical analysis on model checking traces. We are implementing our ideas in an existing static analyzer that employs pushdown model checking and the gcc compiler.

Compiler support for power and energy management is effective in reducing power and energy consumption of programs. Compilers typically take single programs as input without the knowledge of other programs that may run at the same time on the target machine. This work investigates the benefits of optimizing sets of programs with the goal of reducing overall disk energy. We obtained physical measurements on two laptop disks. The experiments show that inter-program optimizations have significant energy savings over individually optimized programs. Energy savings ranged up to 49% over the individually optimized program versions and up to 82% over the unoptimized versions. Across both disks, the average energy savings over individually optimized and unoptimized versions were 25% and 65%, respectively.

Attribute grammars are often discussed in textbooks as a technique for specifying compiler phases. However, beyond the L-attributed grammars supported by YACC/Bison, they are rarely used in the lab exercises for undergraduate courses. After several attempts to fully integrate the use of attribute grammars into an undergraduate course, Dave Wonnacott finally thinks he's gotten this to work well, and is preparing a paper titled "Attribute Grammars and the Teaching of Compiler Design and Implementation". This poster session will provide a students' point of view on this course.

Recent proliferation of connected portable devices such as cellular phones and PDAs have made mobile ad-hoc networks (MANETs) an increasingly attractive platform for application development. However, testing and debugging distributed, mobility-aware applications requires simulating a MANET in a controlled environment. We present a software testbed architecture combining a run-time environment for mobility-aware code with model-based simulation using real traces of node movement.

The JML specification language for Java is used in a number of tools but lacks a tool-independent formal semantic model. A denotational semantics is most suitable to support meta-theoretic studies, e.g., concerning behavioral subtyping, because it can abstract from unobservable operational details. Such a semantics is complex owing to dynamic binding and exceptional control flow. We describe a semantic model which has been defined and validated in the PVS theorem prover.

Traditional object-oriented coupling metrics do not account for polymorphism: that is, if class A declares a field of type B they would account for ONE coupling through that field, even if B is at the root of a wide and deep inheritance hierarchy and A could be coupled at run-time with each of the subclasses of B). Therefore, traditional coupling metrics considerably understimate the complexity of a class and fail to properly predict fault-proneness and changability.

To alleviate this problem Arisholm, Briand and Foyen [TSE'04] define a family of dynamic coupling metrics designed to account for polymorphic coupling. They collect measures through instrumentation and statistically show that certain dynamic coupling metrics are better predictors of fault-proneness and changability than traditional coupling metrics.

Our work presents a new approach to the computation of dynamic coupling metrics. Our appraoch uses static analysis, in particular class analysis, and is designed to work on incomplete programs. We performed experiments on several Java components. We present a precision evaluation which shows that even inexpensive class analyses such as RTA compute dynamic couplings with almost perfect precision. Our results show that inexpensive static analysis can be successfully used to compute dynamic coupling metrics.

Sharing private information while preserving privacy is a challenging task. Currently existing information-flow control models preserve privacy by isolating public data from private data. Data isolation, however, is not applicable to many real applications. We present a new model for information-flow control called Non-Inference. Non-inference allows public data to be derived from private data, but requires that the adversary should not be able to infer the value of private data from public data. We show how it can be enforced using static program analysis in the context of location privacy.

Online services are rapidly becoming the supporting infrastructure for numerous users work and leisure, placing higher demands on their availability and correct functioning. Increasingly, these services are comprised of complex conglomerates of distributed hardware and software components. Added to this complexity, these services evolve quite frequently accumulating considerable heterogeneity within them, while allowing little time for their in-depth understanding by service personnel. Thus, it is not surprising that mistakes by service operators are common, and have been deemed to be the primary cause of service downtime.

Responses from an extensive survey we conducted of network and system administrators further substantiate this problem. Among common failures reported by administrators, 43% of them (37 of 87 reported) can be attributed to operator actions, with software and hardware being the other prominent causes. The results show that mistakes happen due to a variety of reasons including, the lack of understanding of system functioning by operators, complexity of the maintenance task, inattentiveness on the part of the operator, and lack of appropriate tools to help in operations. While offline testbeds should help check some of these mistakes, 56% of the 41 respondents were dissatisfied with such environments since they differ considerably from the online system.

These findings point to the requirement for effective system support to carry out mistake-free service maintenance. Previously, we proposed an approach for operators to check the correctness of their actions in a virtual sandbox environment that extends the online system [1]. We experimented with two techniques within a prototype implementation of the environment for a multi-tier online service. The prototype caught two-thirds of all mistakes we observed in human-factor experiments using volunteer operators. Our techniques relied on comparing the behavior ( i.e., message flow) under test with a known correct behavior, in the form of traces or an online replica. Such comparison techniques, however, cannot be applied in the face of behavior altering maintenance operations. In such instances, the service operator often relies on a mental model of the way the system behaves to verify its correctness. What constitutes such mental models? How can they be succinctly, simply, and accurately represented in a systematic manner? And, how can the system be validated as per these models? These questions are at the core of the problem we address here.

In this work, we propose a model-based approach to specify the system s operational model or behavior in the form of assertions, and a runtime to evaluate and enforce such assertions. Assertions may be specified by service designers well-versed with the system s characteristics and their interactions. For example, consider the working of a load-balancer component. It implements various scheduling algorithms, but a salient property is to achieve uniform resource utilization across the receiving components. Then, its correctness can be tested by asserting an equality of either the flow of messages to each receiving node, or of their resource utilization.

We have designed a declarative language that maps language objects closely to service components, simplifying the specification of the expected model. The model is represented as a dynamic set of assertions on performance ( e.g. throughput) and structural (e.g., connectivity) aspects of a service, and their change across discrete events (e.g., adding a new node). Assertion sets or programs, can then assert expected system behavior both under normal and maintenance operations that modify service behavior. Programs execute over a runtime that provides support for evaluating assertions and enforcing a limited set of actions associated with failed assertions. The runtime gathers and analyzes low-level data and events from a monitoring framework, providing statistical processing of the time-series data. Overall, assertions can be written in a flexible manner to describe system behavior at varying degrees of accuracy, correlating information both across time and other components within the service. Using the extensive data about operator practices and mistakes gathered from our survey mentioned above, we are currently evaluating the model-based approach to detect and mask operator mistakes both within the validation environment and the online service itself. Some open questions for this work are: What is the right level at which operator actions should be checked? What if operators deviate from expected operational paths associated with corresponding system behaviors? Will language-based model specification lead to more mistakes? And, can such languages lend themselves to convenient and accurate laying down of complex mental models maintained by service personnel?

References

[1] K. Nagaraja, F. Oliveira, R. Bianchini, R. P. Martin, and T. D. Nguyen. Understanding and Dealing with Operator Mistakes in Internet Services. In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI 04), Dec. 2004.