Dimensionality reduction is considered as an important step for ensuring competitive performance in unsupervised learning such as anomaly detection. Non-negative matrix factorization (NMF) is a widely used method to accomplish this goal. But NMF do not have the provision to include the neighborhood structure information and, as a result, may fail to provide satisfactory performance in presence of nonlinear manifold structure. To address this shortcoming, we propose to consider the neighborhood structural similarity information within the NMF framework and do so by modeling the data through a minimum spanning tree. We label the resulting method as the neighborhood structure-assisted NMF. We further develop both offline and online algorithms for implementing the proposed method. Empirical comparisons using twenty benchmark data sets as well as an industrial data set extracted from a hydropower plant demonstrate the superiority of the neighborhood structure-assisted NMF. Looking closer into the formulation and properties of the proposed NMF method and comparing it with several NMF variants reveal that inclusion of the MST-based neighborhood structure plays a key role in attaining the enhanced performance in anomaly detection.

Regression test selection (RTS) techniques attempt to reduce regression testing costs by selecting a subset of a software system's test cases for use in testing changes made to that system. In practice, RTS techniques may select inordinately large sets of test cases, particularly when applied to industrial systems such as those developed at ABB, where code changes may have far-reaching impact. In this paper, we present a new RTS technique that addresses this problem by focusing on specific classes of faults that can be detected by internal oracles - oracles (rules) that enforce constraints on system states during system execution. Our technique uses program chopping to identify code changes that are relevant to internal oracles, and selects test cases that cover these changes. We present the results of an empirical study that show that our technique is more effective and efficient than other RTS techniques, relative to the classes of faults targeted by the internal oracles.

In an industrial context, software systems are rarely developed by a single organization. For software product lines, this means that various organizations collaborate to provide and integrate the assets used in a product line. It is not uncommon that these assets themselves are built as product lines, a practice which is referred to as multi product lines. This cross-organizational distribution of reusable assets leads to numerous challenges, such as inconsistent configuration, costly and time-consuming integration, diverging evolution speed and direction, and inadequate testing.

Configurable systems that let users customize system behaviors are becoming increasingly prevalent. Testing a configurable system with all possible configurations is very expensive and often impractical. For a single version of a configurable system, sampling approaches exist that select a subset of configurations from the full configuration space for testing. However, when a configurable system changes and evolves, existing approaches for regression testing select all configurations that are used to test the old versions for testing the new version. As demonstrated in our experiments, this retest-all approach for regression testing configurable systems turns out to be highly redundant. To address this redundancy, we propose a configuration selection approach for regression testing. Formally, given two versions of a configurable system, S (old) and S' (new), and given a set of configurations CSfor testing S, our approach selects a subset CS'of CSfor regression testing S'. Our study results on two open source systems and a large industrial system show that, compared to the retest-all approach, our approach discards 15% to 60% of configurations as redundant. Our approach also saves 20% to 55% of the regression testing time, while retaining the same fault detection capability and code coverage of the retest-all approach.

Change impact analysis, i.e., knowing the potential consequences of a software change, is critical for the risk analysis, developer effort estimation, and regression testing of evolving software. Static program slicing is an attractive option for enabling routine change impact analysis for newly committed changesets during daily software build. However, static program slicing faces accuracy and scalability problems when applied routinely on large and evolving industrial software systems. In this paper, we present a tool called Imp, used within ABB, to address these problems. Imp transparently integrates with the version control and the daily build environments and is also available as a Visual Studio plugin for quick what-if analysis by developers for potential changes in software written in C/C++.

Change impact analysis, i.e., knowing the potential consequences of a software change, is critical for the risk analysis, developer effort estimation, and regression testing of evolving software. Static program slicing is an attractive option for enabling routine change impact analysis for newly committed changesets during daily software build. For small programs with a few thousand lines of code, static program slicing scales well and can assist precise change impact analysis. However, as we demonstrate in this paper, static program slicing faces unique challenges when applied routinely on large and evolving industrial software systems. Despite recent advances in static program slicing, to our knowledge, there have been no studies of static change impact analysis applied on large and evolving industrial software systems. In this paper, we share our experiences in designing a static change impact analysis framework for such software systems. We have implemented our framework as a tool called Imp and have applied Imp on an industrial codebase with over a million lines of C/ C++ code with promising empirical results.

Testing configurable systems, which are becoming prevalent, is expensive due to the large number of configurations and test cases. Existing approaches reduce this expense by selecting or prioritizing configurations. However, these approaches redundantly run the full test suite for the selected configurations. To address this redundancy, we propose a test case selection approach by analyzing the impact of configuration changes with static program slicing. Given an existing test suite T used for testing a system S under a configuration C, our approach decides for each t in T if t has to be used for testing S under a different configuration C'. We have evaluated our approach on a large industrial system within ABB with promising results.

Online services such as search and live applications rely on large infrastructures in data centers, consisting of both stateless servers (e.g., web servers) and stateful servers (e.g., database servers). Acceptable performance of such infrastructures, and hence the availability of online services, rely on a very large number of parameters such as per-process resources and configurable system/application parameters. These parameters are available for collection as performance counters distributed across various machines, but services have had a hard time determining which performance counters to monitor and what thresholds to use for performance alarms in a production environment. In this paper, we present a novel framework called PerfAnalyzer, a storage-efficient and pro-active performance monitoring framework for correlating service health with performance counters. PerfAnalyzer automatically infers and builds health models for any service by running the standard suite of predeployment tests for the service and data mining the resulting performance counter data-set. A filtered set of performance counters and thresholds of alarms are produced by our framework. The health model inferred by our framework can then be used to detect performance degradation and collect detailed data for root-cause analysis in a production environment. We have applied PerfAnalyzer on five simple stress scenarios - CPU, memory, I/O, disk, and network, and two real system - Microsoft's SQL Server 2005 and IIS 7.0 Web Server, with promising results.

A software system interacts with third-party libraries through various APIs. Insufficient documentation and constant refactorings of third-party libraries make API library reuse difficult and error prone. Using these library APIs often needs to follow certain usage patterns. These patterns aid developers in addressing commonly faced programming problems such as what checks should precede or follow API calls, how to use a given set of APIs for a given task, or what API method sequence should be used to obtain one object from another. Ordering rules (specifications) also exist between APIs, and these rules govern the secure and robust operation of the system using these APIs. These patterns and rules may not be well documented by the API developers. Furthermore, usage patterns and specifications might change with library refactorings, requiring changes in the software that reuse the library. To address these issues, we develop novel techniques (and their supporting tools) based on mining source code, assisting developers in productively reusing third party libraries to build reliable and secure software.

A software system interacts with third-party libraries through various APIs. Using these library APIs often needs tofollow certain usage patterns. Furthermore, ordering rules (specifications) exist between APIs, and these rules govern the secure and robust operation of the system using these APIs. But these patterns and rules may not be well documented by the API developers. Previous approaches mine frequent association rules, itemsets, or subsequences that capture API call patterns shared by API client code. However, these frequent API patterns cannot completely capture some useful orderings shared by APIs, especially when multiple APIs are involved across different procedures. In this paper, we present a framework to automatically extract usage scenarios among user-specified APIs as partial orders, directly from the source code (API client code). We adapt a model checker to generate interprocedural control-flow-sensitive static traces related to the APIs of interest. Different API usage scenarios are extracted from the static traces by our scenario extraction algorithm and fed to a miner. The miner summarizes different usage scenarios as compact partial orders. Specifications are extracted from the frequent partial orders using our specification extraction algorithm. Our experience of applying the framework on 72 X11 clients with 200K LOC in total has shown that theextracted API partial orders are useful in assisting effective API reuse and checking.

A software system interacts with its environment through interfaces. Improper handling of exceptional returns from system interfaces can cause robustness problems. Robustness of software systems are governed by various temporal properties related to interfaces. Static verification has been shown to be effective in checking these temporal properties. But manually specifying these properties is cumbersome and requires the knowledge of interface specifications, which are often either unavailable or undocumented. In this paper, we propose a novel framework to automatically infer system-specific interface specifications from program source code. We use a model checker to generate traces related to the interfaces. From these model checking traces, we infer interface specification details such as return value on success or failure. Based on these inferred specifications, we translate generically specified interface robustness rules to concrete robustness properties verifiable by static checking. Hence the generic rules can be specified at an abstract level that needs no knowledge of the source code, system, or interfaces. We implement our framework for an existing static analyzer that employs push down model checking and apply the analyzer to the well known POSIX-API system interfaces. We found 28 robustness violations in 10 open source packages using our framework

A software system interacts with its environment through system interfaces. Robustness of software systems are governed by various temporal properties related to these interfaces, whose violation leads to system crashes and security compromises. These properties can be formally specified for system interfaces and statically verified against a software system. But manually specifying a large number of interface properties for static verification is often inaccurate or incomplete, apart from being cumbersome. In this paper, we propose a novel framework that effectively generates interface properties for static checking from a few generic, high level robustness rules that capture interface behavior. We implement our framework for an existing static analyzer with simple dataflow extensions and apply it on POSIX-API system interfaces used in 10 Redhat-9.0 open source packages. The results show that the framework can effectively generate a large number of useful interface properties from a few generically specified rules

Routing in wireless sensor networks is different from that in commonsense mobile ad-hoc networks. It mainly needs to support reverse multicast traffic to one particular destination in a multihop manner. For such a communication pattern, end-to-end encryption is a challenging problem. To save the overall energy resources of the network, sensed data needs to be consolidated and aggregated on its way to the final destination. We present an approach that 1) conceals sensed data end-to-end by 2) still providing efficient and flexible in-network data aggregation. The aggregating intermediate nodes are not required to operate on the sensed plaintext data. We apply a particular class of encryption transformations and discuss techniques for computing the aggregation functions "average" and "movement detection." We show that the approach is feasible for the class of "going down" routing protocols. We consider the risk of corrupted sensor nodes by proposing a key predistribution algorithm that limits an attacker's gain and show how key predistribution and a key-ID sensitive "going down" routing protocol help increase the robustness and reliability of the connected backbone

End-to-end encryption schemes that support operations over ciphertext are of utmost importance for commercial private party wireless sensor network implementations to become meaningful and profitable. For wireless sensor networks, we demonstrated in our previous work that privacy homomorphisms, when used for this purpose, offer two striking advantages apart from end-to-end concealment of data and ability to operate on ciphertexts: flexibility by keyless aggregation and conservation and balancing of aggregator backbone energy. We offered proof of concept by applying a certain privacy homomorphism for sensor network applications that rely on the addition operation. But a large class of aggregator functions like median computation or finding maximum/minimum rely exclusively on comparison operations. Unfortunately, as shown by Rivest, et al., any privacy homomorphism is insecure even against ciphertext that only attacks if they support comparison operations. In this paper we show that a particular order preserving encryption scheme achieves the above mentioned energy benefits and flexibility when used to support comparison operations over encrypted texts for wireless sensor networks, while also managing to hide the plaintext distribution and being secure against ciphertext only attacks. The scheme is shown to have reasonable memory and computation overhead when applied for wireless sensor networks.