Home » Articles posted by kaiser

Author Archives: kaiser

Record/Replay Bug Reproduction for Java

There will inevitably continue to be bugs that are not detected by any testing approach, but eventually impact users who then file bug reports. Reproducing field failures in the development environment can be difficult, however, especially in the case of software that behaves non-deterministically, relies on remote resources, or has complex reproduction steps (the users may not even know what led up to triggering the flaw, particularly in the case of software interacting with external devices, databases, etc. in addition to human users). So a record/replay approach is used to capture the state of the system just before a bug is encountered, so the steps leading up to this state can be replayed later in the lab. The naive approach of constant logging in anticipation of a defect tends to produce unacceptably high overheads (reaching 2,000+ %) in the deployed application. Novel solutions that lower this overhead typically limit the depth of information recorded (e.g., to use only a stack trace, rather than a complete state history) or the breadth of information recorded (e.g., to only log information during execution of a particular subsystem that a developer identifies as potentially buggy). But limiting the depth of information gathered may fail to reproduce an error if the defect does not present itself immediately and limiting logging to a specific subcomponent of an application makes it only possible to reproduce the bug if it occurred within that subcomponent.

Our new technique, called “Chronicler”, instead captures program execution in a manner that allows for deterministic replay in the lab with very low overhead. The key insight is to log sources of non-determinism only at the library level – allowing for a lightweight recording process while still supporting a complete replay for debugging purposes (programs with no sources of non-determinism, e.g., no user interactions, are trivial to replay – just provide the same inputs). When a failure occurs, Chronicler automatically generates a test case that consists of the inputs (e.g., file or network I/O, user inputs, random numbers, etc.) that caused the system to fail. This general approach can be applied to any “managed” language that runs in a language virtual machine (for instance, JVM or Microsoft’s .NET CLR), requiring no modifications to the interpreter or environment, and thus addresses a different class of programs than related work for non-managed languages like C and C++.

We expect to extend and use this tool as part of the Mutable Replay project, and are seeking new project students in tandem with that effort.

Contact Professor Gail Kaiser (kaiser@cs.columbia.edu)



Jonathan Bell, Nikhil Sarda and Gail Kaiser. Chronicler: Lightweight Recording to Reproduce Field Failures. 35th International Conference on Software Engineering, May 2013, pp. 362-371. See teaser video at https://www.youtube.com/watch?v=4IYGfdDnAJg.


Download ChroniclerJ.

Gameful Computational Thinking

Inspired by CS for All?  The Programming Systems Lab, led by Professor Gail Kaiser, is building a game-based learning and assessment system that infuses computational thinking in grade 6-8 curricula.  For the Fall 2017 semester, we’re recruiting students interested in collaborating as a Scrum team to complete an MVP expected to include several features:
  • A gameful direct instruction system that embeds Parson’s Programming Puzzles in Scratch
  • A gameful constructionism mode that integrates scoring systems for play and automated assessment through Blockly
  • A gameful intelligent tutor that provides hints on-demand and just-in-time via clustering and sequential pattern mining algorithms
  • A gameful affinity space that enables curricula assimilation with quest management and learning metrics using Node.js
Our projects with students from previous semesters have resulted in the development of a rich architecture and we anticipate a productive period ahead with opportunities for co-authorship of publications that document results from experiments with grade 6-8 students.  Participants will register for 3 credits of COMS E6901, section 014.  CVN students are welcome.  To learn more, please contact Jeff Bender, jeffrey.bender@columbia.edu.
SAGE | Social Addictive Gameful Engineering

Identifying Functionally Similar Code in Complex Codebases

Presented by Mike Su at 24th IEEE International Conference on Program Comprehension (ICPC), May 2016.
ACM SIGSOFT Distinguished Paper Award

Challenges in Behavioral Code Clone Detection

Presented by Mike Su at 10th International Workshop on Software Clones (IWSC), March 2016.
People’s Choice Award for Best Position Paper

Code Relatives: Detecting Similarly Behaving Software

author = {Su, Fang-Hsiang and Bell, Jonathan and Harvey, Kenneth and Sethumadhavan, Simha and Kaiser, Gail and Jebara, Tony},
title = “{Code Relatives: Detecting Similarly Behaving Software}”,
booktitle = “{24th ACM SIGSOFT International Symposium on Foundations of Software Engineering}”,
series = {FSE 2016},
year = {2016},
isbn = {978-1-4503-4218-6},
location = {Seattle, WA, USA},
pages = {702–714},
numpages = {13},
url = {http://doi.acm.org/10.1145/2950290.2950321},
doi = {10.1145/2950290.2950321},
acmid = {2950321},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {Code relatives, code clones, link analysis, runtime behavior, subgraph matching},
note = “Artifact accepted as platinum.”

Mutable Replay

This project is heavily influenced by previous work from Prof. Jason Nieh in this area, in his case for
x86 for Linux whereas we work with JVM-based managed languages. We are also collaborating with
Prof. Jonathan Bell of George Mason University.  Record/replay records all non-deterministic
inputs received during deployed execution (in a customer environment) so the execution can later be replayed
deterministically in the development lab by reusing those inputs, e.g., to reproduce a reported bug or examine
anomalous behavior for intrusions and other security exploits. Non-deterministic “inputs” here include responses from
system and library calls, e.g., random number generators, network traffic, file system and database accesses, etc., not
just end-user inputs. Conventional record/replay only works when the code replayed in the lab is exactly the same as
the code that had been recorded in the field, or adds only very limited debugging instrumentation that does not effect
the non-deterministic inputs or their dependencies. But it is desirable to replay candidate bug fixes to check that the
code change (mutation) indeed fixes the bug, even though a correct bug fix will almost always require some
new/different inputs and/or produce some new/different outputs, and replay may need to skip over or replace some
previously recorded inputs that are invalidated by changed dependencies. We are investigating static and dynamic
program analysis techniques aimed to determine how to transform the recorded log to enable replay to proceed past
changed portions of the code. This problem is undecidable in the general case (imagine inserting an infinite loop), but
preliminary results show is feasible in many practical cases when the developer’s version repository is available for
analysis (which was not leveraged for Prof. Nieh’s earlier system) and the managed language platform hides
operating system level complexities such as memory mapping and interrupts that may reduce performance.

Contact Gail Kaiser (kaiser@cs.columbia.edu)

Team Members

Gail Kaiser

Graduate Students
Anthony Saeiva Narin

Former Graduate Students
Jonathan Bell
Kenny Harvey   


Identifying Functionally Similar Code in Complex Codebases

author = “Fang-Hsiang Su and Jonathan Bell and Gail Kaiser and Simha Sethumadhavan”,
title = “(Identifying Functionally Similar Code in Complex Codebases}”,
booktitle = “{24th IEEE International Conference on Program Comprehension (ICPC)}”,
month = “May”,
year = “2016”,
pages = “1–10”,
url = “http://dx.doi.org/10.1109/ICPC.2016.7503720”,
note = “ACM SIGSOFT Distinguished Paper Award”

Challenges in Behavioral Code Clone Detection

author = “Fang-Hsiang Su and Jonathan Bell and Gail Kaiser”,
title = “{Challenges in Behavioral Code Clone Detection (Position Paper)}”,
booktitle = “{10th International Workshop on Software Clones (IWSC), affiliated with IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER)}”,
month = “March”,
year = “2016”,
volume = “3”,
pages = “21–22”,
url = “http://dx.doi.org/10.1109/SANER.2016.75”,
note = “People’s Choice Award for Best Position Paper.”

Efficient Dependency Detection for Safe Java Test Acceleration

Presented by Jon Bell at 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE), September 2015.

Efficient Dependency Detection for Safe Java Test Acceleration

author = {Bell, Jonathan and Kaiser, Gail and Melski, Eric and Dattatreya, Mohan},
title = “{Efficient Dependency Detection for Safe Java Test Acceleration}”,
booktitle = “{2015 10th Joint Meeting on Foundations of Software Engineering}”,
series = {ESEC/FSE 2015},
year = {2015},
isbn = {978-1-4503-3675-8},
location = {Bergamo, Italy},
pages = {770–781},
numpages = {12},
url = {http://doi.acm.org/10.1145/2786805.2786823},
doi = {10.1145/2786805.2786823},
acmid = {2786823},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {Test dependence, detection algorithms, empirical studies},