System reliability is a fundamental requirement of Cyber-Physical System (CPS), i.e., a system featuring a tight combination of, and coordination between, the systems computational and physical elements. Cyber-physical system includes systems ranging from the critical infrastructure such as power grid and transportation system to the health and biomedical devices. An unreliable system often leads to disruption of service, financial cost and even loss of human life. In this work, we aim to improve system reliability for cyber-physical systems that meet following criteria: processing large amount of data; employing software as a system component; running online continuously; having operator-in-the-loop because of human judgment and accountability requirement for safety critical systems. The reason that we limit the system scope to this type of cyber-physical system is that this type of cyber-physical systems are important and becoming more prevalent.

To improve system reliability for this type of cyber-physical systems, we employ a novel system evaluation approach named automated online evaluation. It works in parallel with the cyber- physical system to conduct automated evaluation at the multiple stages along the workflow of the system continuously and provide operator-in-the-loop feedback on reliability improvement. It is an approach whereby data from cyber-physical system is evaluated. For example, abnormal input and output data can be detected and flagged through data quality analysis. As a result, alerts can be sent to the operator-in-the-loop. The operator can then take actions and make changes to the system based on the alerts in order to achieve minimal system downtime and higher system reliability. To implement the approach, we design a system architecture named ARIS (Autonomic Reliability Improvement System).

One technique used by the approach is data quality analysis using computational intelligence that applies computational intelligence in evaluating data quality in some automated and efficient way to ensure data quality and make sure the running system to perform as expected reliably. The computational intelligence is enabled by machine learning, data mining, statistical and probabilistic analysis, and other intelligent techniques. In a cyber-physical system, the data collected from the system, e.g., software bug reports, system status logs and error reports, are stored in some databases. In our approach, these data are analyzed via data mining and other intelligent techniques so that useful information on system reliability including erroneous data and abnormal system state can be concluded. These reliability related information are directed to operators so that proper actions can be taken, sometimes proactively based on the predictive results, to ensure the proper and reliable execution of the system.

Another technique used by the approach is self-tuning that automatically self-manages and self-configures the evaluation system to ensure it adapts itself based on the changes in the system and feedback from the operator. The self-tuning adapts the evaluation system to ensure its proper functioning, which leads to a more robust evaluation system and improved system reliability.

Project Members

Faculty: Prof. Gail Kaiser

PhD Candidate: Leon Wu

Publications

Leon Wu and Gail Kaiser. FARE: A Framework for Benchmarking Reliability of Cyber-Physical Systems. In Proceedings of the 9th Annual IEEE Long Island Systems, Applications and Technology Conference (LISAT), May 2013.

Leon Wu and Gail Kaiser. An Autonomic Reliability Improvement System for Cyber-Physical Systems. In Proceedings of the IEEE 14th International Symposium on High-Assurance Systems Engineering (HASE), October 2012.

Leon Wu, Gail Kaiser, David Solomon, Rebecca Winter, Albert Boulanger, and Roger Anderson. Improving Efficiency and Reliability of Building Systems Using Machine Learning and Automated Online Evaluation. In the 8th Annual IEEE Long Island Systems, Applications and Technology Conference (LISAT), May 2012.

Rebecca Winter, David Solomon, Albert Boulanger, Leon Wu, and Roger Anderson. Using Support Vector Machine to Forecast Energy Usage of a Manhattan Skyscraper. In New York Academy of Science Sixth Annual Machine Learning Symposium, New York, NY, USA, October 2011.

Leon Wu, Gail Kaiser, Cynthia Rudin, and Roger Anderson. Data Quality Assurance and Performance Measurement of Data Mining for Preventive Maintenance of Power Grid. In Proceedings of the ACM SIGKDD 2011 Workshop on Data Mining for Service and Maintenance, August 2011.

Leon Wu and Gail Kaiser. Constructing Subtle Concurrency Bugs Using Synchronization-Centric Second-Order Mutation Operators. In Proceedings of the 23th International Conference on Software Engineering and Knowledge Engineering (SEKE), July 2011.

Leon Wu, Boyi Xie, Gail Kaiser, and Rebecca Passonneau. BugMiner: Software Reliability Analysis Via Data Mining of Bug Reports. In Proceedings of the 23th International Conference on Software Engineering and Knowledge Engineering (SEKE), July 2011.

Leon Wu, Gail Kaiser, Cynthia Rudin, David Waltz, Roger Anderson, Albert Boulanger, Ansaf Salleb-Aouissi, Haimonti Dutta, and Manoj Pooleery. Evaluating Machine Learning for Improving Power Grid Reliability. In ICML 2011 Workshop on Machine Learning for Global Challenges, July 2011.

Leon Wu, Timothy Teräväinen, Gail Kaiser, Roger Anderson, Albert Boulanger, and Cynthia Rudin. Estimation of System Reliability Using a Semiparametric Model. In Proceedings of the IEEE EnergyTech 2011 (EnergyTech), May 2011.

Cynthia Rudin, David Waltz, Roger Anderson, Albert Boulanger, Ansaf Salleb-Aouissi, Maggie Chow, Haimonti Dutta, Phil Gross, Bert Huang, Steve Ierome, Delfina Isaac, Artie Kressner, Rebecca Passonneau, Axinia Radeva, and Leon Wu. Machine Learning for the New York City Power Grid. IEEE Transactions on Pattern Analysis and Machine Intelligence, May 2011.

HALO, or Highly Addictive sociaLly Optimized Software Engineering, represents a new and social approach to software engineering. Using various engaging and addictive properties of collaborative computer games such as World of Warcraft, HALO’s goal is to make all aspects of software engineering more fun, increasing developer productivity and satisfaction.

HALO represents software engineering tasks as quests and uses a storyline to bind multiple quests together – users must complete quests in order to advance the plot. Quests can either be individual, requiring a developer to work alone, or group, requiring a developer to form a team and work collaboratively towards their objective.

This approach follows a growing trend to “gamify” everyday life (that is, bring game-like qualities to it), and has been popularized by alternate reality game proponents such as Jane McGonigal.

These engaging qualities can be found in even the simplest games, from chess to tetris, and result in deep levels of player immersion. Gamification has also been studied in education, where teachers use the engaging properties of games to help students focus.

We leverage the inherently competitive-collaborative nature of software engineering in HALO by providing developers with social rewards. These social rewards harness operant conditioning – a model that rewards players for good behavior and encourages repeat behavior. Operant conditioning is a technique commonly harnessed in games to retain players.

Multi-user games typically use peer recognition as the highest reward for successful players. Simple social rewards in HALO can include titles – prefixes or suffixes for players’ names – and levels, both of which showcase players’ successes in the game world. For instance, a developer who successfully closes over 500 bugs may receive the suffix “The Bugslayer.” For completing quests, players also receive experience points that accumulate causing them to “level up” in recognition of their ongoing work. HALO is also designed to create an immersive environment that helps developers to achieve a flow state, a technique that has been found to lead to increased engagement and addiction.

Team Members

Faculty

Prof. Gail Kaiser, kaiser [at] cs.columbia.edu

Graduate Students

Jon Bell, jbell [at] cs.columbia.edu
Swapneel Sheth, swapneel [at] cs.columbia.edu

Links

Publications

Jonathan Bell, Swapneel Sheth and Gail Kaiser. A Gameful Approach to Teaching Software Testing. Kendra Cooper and Walt Scacchi (eds.), Computer Games and Software Engineering, CRC, 2015.

At SSE 2011

At GAS 2011

Datasets

World of Warcraft Massive Dataset

About VULCANA

As the Internet has grown in popularity, security vulnerability detecting and testing are undoubtedly becoming crucial parts for commercial software, especially for web service applications. Vulnerability scanners, both commercial and open-source (i.e., SAINT, eEye, Nessus, etc.), were developed to achieve this goal. However, the absence of a well defined assessment benchmark makes the efficient evaluation of these scanners nearly impossible. With ongoing researches on new vulnerability scanners, the demand for such an assessment benchmark is urgent. We are working on developing VULCANA, a set of open-source web service applications with systematically injected vulnerabilities. The idea is that different vulnerability scanners can be used to scan the benchmark, and the percentage of detected vulnerabilities together with the resource consumption are used to provide reasonable evaluation.

In Spring 2009, we developed a prototype framework called Baseline, which is described in our tech report. The idea of BaseLine is that we tried to coach the users to pick the right Web Vulnerability Scanner by letting them set up a baseline for potential qualified scanners. We can then test the scanner with the baseline, revealing its effectiveness and efficiency in detecting the user’s most “care-about” vulnerabilities.

Brief Introduction of Baseline
Most of existing benchmarks use the scanners to scan a manually crafted website with a number of known vulnerabilities, and rate the scanners based on the percentage of successful detection. These benchmarks are only capable of judging which scanner is better in the matter of how well the scanners can detect the fixed set of vulnerabilities the benchmarks picked with static selection criteria. They suffer from drawbacks by neglecting the critical questions: Does the benchmark properly reflect the user’s security requirements; does it reflect the user’s actual deployment environment? In helping the users choose the right scanners, answering these questions is as crucial as evaluating the effectiveness and efficiency of the scanners. In this paper, we propose an approach called Baseline that addresses all of these problems: We implement a ranking system for dynamically generating the most suitable selection of weaknesses based on the user’s needs, which serves as the baseline that a qualified scanner should reach/detect. Then we pair the ranking system with a testing framework for generating test suites according to the selection of weaknesses. This framework maps a weakness into an FSM (Finite State Machine) with multiple end states that represent different types/mutations of exploitations of the weakness and each transition from state to state determined by scanner behavior, the framework then combines the FSMs of the selected weaknesses into a mimicked vulnerable website. When a scanner scans the “vulnerable” website, the transitions between the states are recorded and thus we are able to evaluate the scanner by looking at which end states were visited (effectiveness), in how much time, and over how many transitions(efficiency).

Currently we are looking at methods of measuring assorted aspects of the web vulnerability scanners. Specifically, the ability of bypassing client-side validation, the crawling coverage and the capability of scanning auto-generated pages.

Open research questions include:

• Currently, Baseline framework uses Regular expression to determine the transition between two states. Can we extend Baseline with more sophisticated validation methods?
• Client-side validation seems to be neglected by most (if not all) existing scanners. Are there any drawbacks for the scanners to omit them?
• There are no existing web vulnerabilty repository, can we create one?

Team Members

Faculty
Prof. Gail Kaiser, kaiser [at] cs.columbia.edu

Graduate Students
Huning Dai, hdd2210 [at] columbia.edu
Shreemanth Hosahalli, sh2959 [at] columbia.edu

Former Members
Michael Glass
Anshul Mittal

About CloudView

CloudView is a project that enables detection and diagnosis of network faults using a peer to peer architecture. Consider the following scenario. A user is trying to log into an IM server, but she is not able to. There could be a variety of reasons for the failure. Some plausible causes for this failure are the IM server is temporarily unavailable, the ISP is down, or the user’s password is not correct.

CloudView can be used to diagnose this problem, proceeding as follows: CloudView tries to contact other peers who are part of its network, which will then run probes to try to isolate the problem. Examples of probes could be trying to log in from another node, using a different username and password, and trying to ping the server. The results of these probes will be returned to the original node, and using the rule book it would try to find the cause of the problem. This entire process is automated and the group of peers runs a set of analysis tests and depending on the results on these tests, we can diagnose the problem.

Our system is based on the DYSWIS system. While DYSWIS is focused on the detection and diagnosis of network and transport level faults, CloudView is aimed towards the detection and diagnosis of faults at the application level.

In previous semesters, we have focused on the XMPP/Jabber Chat Protocol and developed a proof-of-concept implementation. We have also extended our system to the Samba (SMB) protocol.

We are looking to add more functionality to the current implementation and also extend this into other domains, which include BitTorrent, Cloud Computing, Email, Web Browsing, and Games.

Team Members

Faculty
Prof. Gail Kaiser, kaiser [at] cs.columbia.edu

Graduate Students
Swapneel Sheth, swapneel [at] cs.columbia.edu

Former members
Rajat Dixit
Palak Baid
Somenath Das
Siming Sun
Jau-Yuan Chen

Links

DYSWIS – http://www.cs.columbia.edu/irt/project/dyswis/
XMPP – http://xmpp.org/
SMB – http://samba.org/

About COMPASS

COMPASS is a Community-driven Parallelization Advisor for Sequential Software. It provides advice to programmers while they reengineer their code for parallelism and provides a platform and an extensible framework for sharing human expertise about code parallelization. COMPASS aims to enable rapid propagation of knowledge about code parallelization in the context of the actual parallelization reengineering, and thus continue to extend the benefits of Moore’s law scaling to science and society.

Team Members

Faculty
Prof. Simha Sethumadhavan, simha [at] cs.columbia.edu
Prof. Gail Kaiser, kaiser [at] cs.columbia.edu

Graduate Students
Nipun Arora, na2271 [at] columbia.edu

Links

Official project website
Original paper from International Workshop on Multicore Software Engineering (IWMSE)

Contact: Nipun Arora

About This Project

In this project, we sought to learn about introductory-level students’ programming habits by observing their behavior when they use an IDE such as Eclipse. We do this by capturing such data like compilation errors, amount of time spent on an assignment, etc., then reporting the data back to a central repository where it can be mined and analyzed. This will help us create reports for the instructor, and also allow us to create ad hoc social networks of students who who have similar programming styles and habits. We also want the system to be able to provide helpful hints to the students, based on their programming styles. We believe that this will enrich the students’ experience and make them better programmers.

In Fall 2007, we built the basic infrastructure for capturing compilation errors and storing them in a database, as well as a prototype UI for instructors’ reports, and a IM-based user interface with which students can “chat”.

In Spring 2008, we collected data from some students in COMS W1004, added new reports and analysis to the instructor’s UI, began the creation of ad hoc user communities (social networks), and created a “help” feature that suggests ways that students can improve their code.

In Summer 2008, we analyzed the data that we collected and tried to determine any correlations between when students start their homework, how much time they spend on it, how many errors they make, what time of day they work on it, and what grades they receive. We also developed the student-view UI and implemented the real-time recommendations. Last, we wrote a paper, which was presented at SIGCSE 2009.

Unfortunately the Retina project is no longer active but if you are interested in working on it and reviving it, please contact us.

Team Members

Faculty

Prof. Gail Kaiser, kaiser [at] cs.columbia.edu

Students
Diana Chang
Aaron Fernandes
Michelle Forman
Sahar Hasan
Tian He
Shreya Kedia
Henry Lau
Tina Loveland
Ben Monnin
Chris Murphy

Links

Publications
Retina paper from SIGCSE 2009

Demo Videos
Instructor View (AVI, MPG)
Student View (AVI, MPG)
Real-time Recommendation (AVI, MPG)

Related tools
Eclipse
NetBeans
BlueJ
Web-CAT

Downloads
Microsoft JDBC driver

Documentation
SQL tutorial
JDBC tutorial (focuses on Oracle but a good starting point)
Microsoft JDBC tutorial (warning: there are some errors in the doc)
JDBC tutorial (this one’s actually really good)
XML and DOM tutorial
Java socket tutorial

Kheiron was developed as a toolkit for performing runtime adaptations in software systems. Our original goal was to create a tool that could be used to dynamically retro-fit self-healing capabilities onto existing/legacy systems transparently and with low overhead. Kheiron manipulates compiled C programs running in an unmanaged execution environment (ELF binaries on Linux x86) as well as programs running in managed execution environments e.g. Microsoft’s Common Language Runtime and Sun Microsystems’ Java Virtual Machine. We currently use Kheiron to build fault-injection tools, which we use in our RAS-benchmarking efforts described below.

About Backstop

In this project, we sought to create tools to help novice Java programmers comprehend some of the complicated error messages provided by the Java Virtual Machine. Whereas there has been much work in creating easy-to-understand compiler messages, little work has been done in the area of runtime errors. When a Java program produces an uncaught exception, the result is a stacktrace, which can be difficult for a novice programmer to understand. Backstop has been designed to produce a simpler error message that attempts to explain the cause of the problem, and how to fix it.

Our paper on Backstop has been published in the proceedings of SIGCSE 2008 and is available here.

Unfortunately the Backstop project is no longer active but if you are interested in working on it and reviving it, please contact us.

Team Members

Prof. Gail Kaiser, kaiser [at] cs.columbia.edu
Chris Murphy
Eunhee Kim

Links

Publications
Backstop paper from SIGCSE 2008
Tech report, with an appendix

Related Work
Jim Etheredge’s CMeRun paper

Download

Backstop is released under the GNU General Public License

Backstop v1.0.2 (3/27/08)

Crunch is a web proxy, usable with essentially all web browsers, that performs content extraction (or clutter reduction) from HTML web pages. Crunch includes a flexible plug-in API so that various heuristics can be integrated to act as filters, collectively, to remove non-content and perform content extraction.

This proxy has evolved from a program where individual settings had to be tweaked by hand by the end user, to an extraction system that is designed to adapt to the user’s workflow and needs, classifying web pages based on genre and utilizing this information to extract content in similar manners from similar sites. It reduces human involvement in applying heuristic settings for websites and instead tries to automate the job by detecting and utilizing the content genre of a given website.

One of the major goals of Crunch is to be able to make web pages more accessible to people with disabilities and we believed that preprocessing web pages with Crunch would make inaccessible web pages more accessible.

Publications

Suhit Gupta, Gail Kaiser, “CRUNCH – Web-based Collaboration for Persons with Disabilities”, W3C Web Accessibility Initiative, Teleconference on Making Collaboration Technologies Accessible for Persons with Disabilities, Apr 2003.

Suhit Gupta, Gail Kaiser, David Neistadt, Peter Grimm “DOM-based Content Extraction of HTML Documents” WWW2003

Suhit Gupta; Gail E Kaiser, Peter Grimm, Michael F Chiang, Justin Starren, “Automating Content Extraction of HTML Documents” World Wide Web Journal, January 2004

Michael F. Chiang, Roy G. Cole, Suhit Gupta, Gail E Kaiser, Justin Starren, “World Wide Web Accessibility by Visually Disabled Patients: Problems and Solutions”, Submitted to the Journal of Opthalmology, January 2004

Suhit Gupta; Gail E Kaiser, Salvatore Stolfo, “Extracting Context To Improve Accuracy For HTML Content Extraction”, Poster at the World Wide Web Conference 2005

Suhit Gupta, Gail E Kaiser, Salvatore Stolfo, Hila Becker, Genre Classification of Websites Using Search Engine Snippets for Content Extraction”, Submitted to SIGIR 2005

Suhit Gupta, Gail Kaiser, “Extracting content from accessible webpages”, Proceedings of the 2005 International Cross-Disciplinary Workshop on Web Accessibility (W4A), May 2005