Physical computing has emerged as an effective approach to introducing computing and coding to students. One of the most popular enabling tools is the BBC micro:bit, well-known for its positive impact on teaching programming and driving engagement in the classroom. We extend these benefits by developing a new approach to coding with micro:bit: MicroCode. Unlike other experiences, MicroCode couples the micro:bit with a low-cost handheld accessory to enable live and portable programming via an on-device visual programming language; no separate host computer is needed. We present the design of MicroCode and the findings of a study in which we interviewed five primary school teachers and 60 children aged 10-11 working with MicroCode. The outcomes of the study show that MicroCode raised children’s engagement and stimulated the development of a strong sense of agency on coding activities, while teachers felt empowered to adopt situated and cross-curricular learning approaches.

The traditional approach to programming embedded systems is monolithic: firmware on a microcontroller contains both application code and the drivers needed to communicate with sensors and actuators, using low-level protocols such as I2C, SPI, and RS232. In comparison, software development for the cloud has moved to a service-based development and operation paradigm: a service provides a discrete unit of functionality that can be accessed remotely by an application, or other service, but is independently managed and updated. We propose, design, implement, and evaluate a service-based approach to prototyping embedded systems called Jacdac. Jacdac defines a service specification language, designed especially for embedded systems, along with a host of specifications for a variety of sensors and actuators. With Jacdac, each sensor/actuator in a system is paired with a low-cost microcontroller that advertises the services that represent the functionality of the underlying hardware over an efficient and low-cost single-wire bus protocol. A separate microcontroller executes the user's application program, which is a client of the Jacdac services on the bus. Our evaluation shows that Jacdac supports a service-based abstraction for sensors/actuators at low cost and reasonable performance, with many benefits for prototyping: ease of use via the automated discovery of devices and their capabilities, substitution of same-service devices for each other, as well as high-level programming, monitoring, and debugging. We also report on the experience of bringing Jacdac to commercial availability via third-party manufacturers.

Embedded devices are now commonplace, and hardware prototyping toolkits have become a popular approach for hobbyists and professionals to create embedded hardware prototypes. However, moving from prototype into small scale manufacture use introduces complexity and cost, restricting embedded device development ’beyond the prototype’. Challenges include the need to design custom PCB for manufacture, and the design and fabrication of a device enclosure to ensure the robust enough for deployment. In response, we present MakeDevice : a web-based tool that leverages an existing modular hardware prototyping platform, Jacdac, to enable low-complexity route to generate a custom ‘carrier’ PCB upon which modules can be mounted and electrically connected. MakeDevice also automatically generates CAD files for custom enclosures with apertures to suit. We show how such enclosures can be generated using 3D printing and 2D stencils. In this way, MakeDevice lowers the barriers in moving from prototype to viable low-volume deployment of embedded hardware.

We present the first toolkit that equips blind and visually impaired (BVI) developers with the tools to create accessible data displays. Called PSST (Physical computing Streaming Sensor data Toolkit), it enables BVI developers to understand the data generated by sensors from a mouse to a micro:bit physical computing platform. By assuming visual abilities, earlier efforts to make physical computing accessible fail to address the need for BVI developers to access sensor data. PSST enables BVI developers to understand real-time, real-world sensor data by providing control over what should be displayed, as well as when to display and how to display sensor data. PSST supports filtering based on raw or calculated values, highlighting, and transformation of data. Output formats include tonal sonification, nonspeech audio files, speech, and SVGs for laser cutting. We validate PSST through a series of demonstrations and a user study with BVI developers.

This paper describes ML Blocks, https://tinyurl.com/ml-blocks, a novel interface for training, evaluating, and deploying Tiny Machine Learning (TinyML) models. TinyML is a fast-growing field that incorporates powerful machine learning algorithms into everyday technologies such as activity trackers and Internet of Things devices. Although TinyML-capable microcontrollers are popular in computer science education, few students have had the opportunity to learn about the field because of a lack of novice-friendly ML interfaces. With ML Blocks, users assemble data sets, define, and train neural network classifiers, within one unified block interface. Users can quickly evaluate their classifiers using built-in visualization tools and then export them for use in microcontroller projects. ML Blocks makes the end-to-end development of TinyML models easier for physical computing students and tinkerers at all levels.

Technology has become increasingly pervasive in the creative and experimental environment of the avant-garde fashion runway, particularly in relation to its garments. However, several disciplines are often necessary when exploring technologies for the construction of expressive garments (e.g. garments that respond to their environment), creating a barrier for fashion designers that has limited their ability to leverage new technologies. To help overcome this barrier, we designed and deployed Brookdale, a prototyping system for wearable technology consisting of new plug-and-play hardware that can be programmed using drag-and-drop software. Brookdale was created using a 24-week participatory design process with 17 novice fashion-tech designers. At the end of the 24 week process, designers showcased their Brookdale-enhanced garment collections at an avant-garde fashion-tech runway show in New York City. We report on the experiences, outcomes, and lessons learned throughout this process, and describe results from interviews with the fashion-tech designers 16 weeks after the fashion show, demonstrating the lasting positive impact of Brookdale.

Low-cost microcontroller boards like the BBC micro:bit are used to engage and inspire students worldwide to learn more about computing. Easy-to-use web-based programming environments and low-cost hardware allow novices to build physical computing systems with the micro:bit – systems that sense and respond to the real world. However, devices such as the micro:bit may not capture the attention of every student, as the interests of some may lie in graphic design, animation, or other areas that are not the main focus of physical computing.

While the programming of microcontroller-based embeddable devices typically is the realm of the C language, such devices are now finding their way into the classroom for CS education, even at the level of middle school. As a result, the use of scripting languages (such as JavaScript and Python) for microcontrollers is on the rise.

Historically, embedded systems development has been a specialist skill, requiring knowledge of low-level programming languages, complex compilation toolchains, and specialist hardware, firmware, device drivers and applications. However, it has now become commonplace for a broader range of non-specialists to engage in the making (design and development) of embedded systems - including educators to motivate and excite their students in the classroom. This diversity brings its own set of unique requirements, and the complexities of existing embedded systems development platforms introduce insurmountable barriers to entry. In this paper we present the motivation, requirements, implementation, and evaluation of a new programming platform that enables novice users to create effective and efficient software for embedded systems. The platform has two major components: (1) Microsoft MakeCode (www.makecode.com), a web app that encapsulates an accessible IDE for microcontrollers; and (2) CODAL, an efficient component-oriented C++ runtime for microcontrollers. We show how MakeCode and CODAL combine to provide an accessible, cross-platform, installation-free, high level programming experience for embedded devices without sacrificing performance and efficiency.

Paper-based fabrication techniques offer powerful opportunities to prototype new technological interfaces. Typically, paper-based interfaces are either static mockups or require integration with sensors to provide real-time interactivity. The latter can be challenging and expensive, requiring knowledge of electronics, programming, and sensing. But what if computer vision could be combined with prototyping domain-aware programming tools to support the rapid construction of interactive, paper-based tangible interfaces? We designed a toolkit called ARcadia that allows for rapid, low-cost prototyping of TUIs that only requires access to a webcam, a web browser, and paper. ARcadia brings paper prototypes to life through the use of marker based augmented reality (AR). Users create mappings between real-world tangible objects and different UI elements. After a crafting and programming phase, all subsequent interactions take place with the tangible objects. We evaluated ARcadia in a workshop with 120 teenage girls and found that tangible AR technologies can empower novice technology designers to rapidly construct and iterate on their ideas.

Across the globe, it is now commonplace for educators to engage in the making (design and development) of embedded systems in the classroom to motivate and excite their students. This new domain brings its own set of unique requirements. Historically, embedded systems development requires knowledge of low-level programming languages, local installation of compilation toolchains, device drivers, and applications. For students and educators, these requirements can introduce insurmountable barriers.

The micro:bit (http://www.microbit.org) is a pocket-sized, programmable computing device, designed to engage people with computing technology. The micro:bit is visually appealing, fun, easy to code and inexpensive. It is widely available at schools in the United Kingdom and is now being rolled out world-wide. Key features of the micro:bit that make it a great device for physical computing include a display of 25 LEDs, two programmable input buttons, a USB connector, an edge connector, built-in sensors (e.g. accelerometer, compass and temperature sensor), Bluetooth and a battery pack connector. With these physical attributes, the micro:bit can be used to interact with the world in engaging ways such as a watch, a guitar or a moisture sensor. Multi-person games and apps are possible since micro:bits can communicate with each other. Programming the micro:bit can take place on almost any device (laptop, tablet, desktop) that has a modern browser and a USB connection. The micro:bit platform supports programming in a block-based language or a safe version of JavaScript, which provides a progression for learners of different ages and experience levels. This demo will appeal to computer education researchers specializing in K-12 as well as to instructors wanting a new way to introduce computing in CS101 with a "maker" flavor. In the demo we will show the platform and the hardware. Attendees will have the chance to create apps on real micro:bits. It will be helpful to bring a device with a browser.

Mastering a complex skill like programming takes many hours. In order to encourage students to put in these hours, we built Code Hunt, a game that enables players to program against the computer with clues provided as unit tests. The game has become very popular and we are now running worldwide contests where students have a fixed amount of time to solve a set of puzzles. This paper describes Code Hunt and the contest experience it offers. We then show some early results that demonstrate how Code Hunt can accurately discriminate between good and bad coders. The challenges of creating and selecting puzzles for contests are covered. We end up with a short description of our course experience, and some figures that show that Code Hunt is enjoyed by women and men alike.

Pex is an automatic white-box test-generation tool for .NET. We have established that games can be built on top of Pex to open the tool to students and to the general public. In particular, we have released Pex4Fun (www.pexforfun.com) and its successor Code Hunt (www.codehunt.com) as web-based educational gaming environments for teaching and learning programming and software engineering. In Pex4Fun and Code Hunt, the main game type is a coding duel, where a player writes code in a method to achieve the same functionality as the secret method implementation, based on feedback provided by the underlying Pex tool. Players iteratively modify their code to match the functional behavior of the secret method. The scope of duels extends from the simplest one-line method to those including advanced concepts such as writing parameterized unit tests and code contracts. We have also used the game type for competitions with thousands of players, and have found that it differentiates well between beginners and top coders. This tool demonstration shows how coding duels in Pex4Fun and Code Hunt can be constructed and used in teaching and training programming and software engineering.

Producing industry impacts has been an important, yet challenging task for the research community. In this paper, we report experiences on successful technology transfer of Pex and its relatives (tools derived from or associated with Pex) from Microsoft Research and lessons learned from more than eight years of research efforts by the Pex team in collaboration with academia. Moles, a tool associated with Pex, was shipped as Fakes with Visual Studio since August 2012, benefiting a huge user base of Visual Studio around the world. The number of download counts of Pex and its lightweight version called Code Digger has reached tens of thousands within one or two years. Pex4Fun (derived from Pex), an educational gaming website released since June 2010, has achieved high educational impacts, reflected by the number of clicks of the "Ask Pex!" button (indicating the attempts made by users to solve games in Pex4Fun) as over 1.5 million till July 2014. Evolved from Pex4Fun, the Code Hunt website has been used in a very large programming competition. In this paper, we discuss the technology background, tool overview, impacts, project timeline, and lessons learned from the project. We hope that our reported experiences can inspire more high-impact technology-transfer research from the research community.

Code Hunt (http://www.codehunt.com/) is an educational coding game (that runs in a browser) for teaching and learning computer science at scale. The game consists of a series of worlds and levels, which get increasingly challenging. In each level, the player has to discover a secret code fragment and write code for it. The game has sounds and a leaderboard to keep the player engaged. Code Hunt targets teachers and students from introductory to advanced programming or software engineering courses. In addition, Code Hunt can be used by seasoned developers to hone their programming skills or by companies to evaluate job candidates. At the core of the game experience is an automated program analysis and grading engine based on dynamic symbolic execution. The engine detects any behavioral differences between the player's code and the secret code fragment. The game works in any modern browser, and currently supports C# or Java programs. Code Hunt is a dramatic evolution of our earlier Pex4Fun web platform, from which we have gathered considerable experience (including over 1.4 million programs submitted by users).

Massive Open Online Courses (MOOCs) have recently gained high popularity among various universities and even in global societies. A critical factor for their success in teaching and learning effectiveness is assignment grading. Traditional ways of assignment grading are not scalable and do not give timely or interactive feedback to students. To address these issues, we present an interactive-gaming-based teaching and learning platform called Pex4Fun. Pex4Fun is a browser-based teaching and learning environment targeting teachers and students for introductory to advanced programming or software engineering courses. At the core of the platform is an automated grading engine based on symbolic execution. In Pex4Fun, teachers can create virtual classrooms, customize existing courses, and publish new learning material including learning games. Pex4Fun was released to the public in June 2010 and since then the number of attempts made by users to solve games has reached over one million. Our work on Pex4Fun illustrates that a sophisticated software engineering technique-automated test generation-can be successfully used to underpin automatic grading in an online programming system that can scale to hundreds of thousands of users.

Pex4Fun (http://www.pex4fun.com/) is a web-based educational gaming environment for teaching and learning programming and software engineering. Pex4Fun can be used to teach and learn programming and software engineering at many levels, from high school all the way through graduate courses. With Pex4Fun, a student edits code in any browser - with Intellisense - and Pex4Fun executes it and analyzes it in the cloud. Pex4Fun connects teachers, curriculum authors, and students in a unique social experience, tracking and streaming progress updates in real time. In particular, Pex4Fun finds interesting and unexpected input values (with Pex, an advanced test-generation tool) that help students understand what their code is actually doing. The real fun starts with coding duels where a student writes code to implement a teacher's secret specification (in the form of sample-solution code not visible to the student). Pex4Fun finds any discrepancies in behavior between the student's code and the secret specification. Such discrepancies are given as feedback to the student to guide how to fix the student's code to match the behavior of the secret specification. This tool demonstration shows how Pex4Fun can be used in teaching and learning, such as solving coding duels, exploring course materials in feature courses, creating and teaching a course, creating and publishing coding duels, and learning advanced topics behind Pex4Fun.

This video demo features a new keyword programming environment for TouchDevelop, a popular touch-centric system for scripting mobile devices. The new environment allows users to simply enter a set of keywords, and its internal program synthesis engine automatically generates script snippets that most likely reflect the users' intent. Because the synthesis engine can be triggered anywhere in a script, it also exploits various contextual information, such as which variables/functions are in-scope, to guide the generation of snippets. Our new environment benefit both novice and experienced TouchDevelop users. It helps novice users to synthesize script snippets from keywords and explore unfamiliar TouchDevelop features. It also improves experienced users' productivity because they need to worry about fewer coding details and enter less code. The demoed feature has been released and deployed since TouchDevelop version 2.10.

Software tools researchers can accelerate their ability to learn by exposing tools to users via web technologies, allowing them to observe and test the interactions between humans and tools. At Microsoft Research, we have developed a web service (http://www.rise4fun.com/) for such a purpose that is available for community use.

Live programming allows programmers to edit the code of a running program and immediately see the effect of the code changes. This tightening of the traditional edit-compile-run cycle reduces the cognitive gap between program code and execution, improving the learning experience of beginning programmers while boosting the productivity of seasoned ones. Unfortunately, live programming is difficult to realize in practice as imperative languages lack well-defined abstraction boundaries that make live programming responsive or its feedback comprehensible.

Pex4Fun (http://www.pexforfun.com/) is a web-based serious gaming environment for teaching computer science. Pex4Fun can be used to teach and learn computer programming at many levels, from high school all the way through graduate courses.With Pex4Fun, a student edits code in any browser -- with Intellisense -- and Pex4Fun executes it and analyzes it in the cloud. Pex4Fun connects teachers, curriculum authors, and students in a unique social experience, tracking and streaming progress updates in real time. In particular, Pex4Fun finds interesting and unexpected input values that help students understand what their code is actually doing. The real fun starts with Coding Duels where students write code to implement a teacher's specification. Pex4Fun finds any discrepancies in behavior between the student's code and the specification. This tutorial instructs materials to equip participants with skills and knowledge of using Pex4Fun in teaching and learning, such as solving puzzles, solving Coding Duels, exploring course materials in feature courses, creating and teaching a course, creating and publishing Coding Duels, and learning advanced topics behind Pex4Fun.

We are experiencing a technology shift: powerful and easy-to-use touchscreen-based mobile devices such as smartphones and tablets are becoming more prevalent than traditional PCs and laptops. Many mobile devices are going to be the first and, in less developed countries, possibly the only computing devices that virtually all people would own and carry with them at all times. We propose to reflect this new reality in how computer science is taught in the classroom. In this tutorial, participants will learn about developing software directly on smartphones without a PC using TouchDevelop on Windows Phone, a novel application-creation environment from Microsoft Research. Its typed, structured programming language is built around the idea of using only a touchscreen as the input device to author code. Easy access to the rich sensor and personal data available on a mobile device results in a fun and engaging programming experience for students.

From paper to computers, the way that we have been writing down thoughts and performing symbolic computations has been constantly evolving. Teaching methods closely follow this trend, leveraging existing technology to make teaching more effective and preparing students for their later careers with the available technology. Right now, in 2012, we are in the middle of another technology shift: instead of using PCs and laptops, mobile devices are becoming more prevalent for most everyday computing tasks. In fact, never before in human history were incredibly powerful and versatile computing devices such as smartphones available and adopted so broadly. We propose that computer programming, and thus the teaching of programming, can and should be done directly on the mobile devices themselves, without the need for a separate PC or laptop to write code. Programming on smartphones that we carry around with us at all times means instant gratification for students, as they can show their games and applications to their friends, and it means that students can do their homework or additional practicing at all times. We describe TouchDevelop, a novel mobile programming environment, and call out challenges that need to be overcome and opportunities that it creates.

Dynamic symbolic execution (DSE) can efficiently explore all simple paths through a program, reliably determining whether there are any program crashes or violations of assertions or code contracts. However, if such automated oracles do not exist, the traditional approach is to present the developer a small and representative set of tests in order to let him/her determine their correctness. Customer feedback on Microsoft's Pex tool revealed that users expect different values and also more values than those produced by Pex, which threatens the applicability of DSE in a scenario without automated oracles. Indeed, even though all paths might be covered by DSE, the resulting tests are usually not sensitive enough to make a good regression test suite. In this paper, we present augmented dynamic symbolic execution, which aims to produce representative test sets by augmenting path conditions with additional conditions that enforce target criteria such as boundary or mutation adequacy, or logical coverage criteria.

Applications in mobile-marketplaces may leak private user information without notification. Existing mobile platforms provide little information on how applications use private user data, making it difficult for experts to validate applications and for users to grant applications access to their private data. We propose a user-aware privacy control approach, which reveals how private information is used inside applications. We compute static information flows and classify them as safe/unsafe based on a tamper analysis that tracks whether private data is obscured before escaping through output channels. This flow information enables platforms to provide default settings that expose private data only for safe flows, thereby preserving privacy and minimizing decisions required from users. We built our approach into TouchDevelop, an application-creation environment that allows users to write scripts on mobile devices and install scripts published by other users. We evaluate our approach by studying 546 scripts published by 194 users.

Pex4Fun (pexforfun.com) is a web-based serious gaming environment for teaching computing at many levels, from high school all the way through graduate courses. Unique to the Pex4Fun experience is a cloud-based program evaluation engine based on dynamic symbolic execution and SMT-solving, which provides customized feedback to the student and automated grading for the teacher. Thus, Pex4Fun connects teachers, curriculum authors, and students in a social experience, tracking and streaming progress updates in real time. In particular, Pex4Fun finds interesting and unexpected input values that help students understand what their code is actually doing. The real fun starts with coding duels where students write code to implement a teacher's specification. Pex4Fun finds any discrepancies in behavior between the student's code and the specification. Then based on the reported discrepancies, the student improves his or her code towards the specification. Pex4Fun can be used to develop interesting, engaging, and demanding class materials on mathematics, algorithms, programming languages, or problem solving in general. A teacher can use an integrated wiki to author these class materials for students to work through. This workshop involves creating and teaching course materials at Pex4Fun. Participants should bring a laptop computer. The intended audience includes all levels of CS educators who are interested in integrating educational technology in their teaching environments.

We are experiencing a technology shift: Powerful and easy-to-use touchscreen-based mobile devices like smartphones and tablets are becoming more prevalent than traditional PCs and laptops. We propose that computer programming, and thus teaching of programming, can and should be done directly on the mobile devices themselves, without the need for a separate PC or laptop to write code. In this workshop, participants will learn about developing software directly on smartphones without a PC using TouchDevelop, a novel application creation environment on Windows Phone 7 from Microsoft Research (http://touchdevelop.com). Its typed, structured programming language is built around the idea of only using a touchscreen as the input device to author code. A semi-structured code editor makes it easy to navigate between different syntax elements. By inferring types and mining previously written programs, the editor provides highly predictive auto-completion suggestions to the user. The language provides built-in primitives that make it easy to access the rich sensor data available on a mobile device. Programming on mobile devices engages students in new ways, allowing them to access and manipulate programmatically their most personal digital data such as pictures, videos, and music. Programming on smartphones which we carry around with us at all times means instant gratification for students, as they can show their games and applications to their friends, and it means that students can do their homework or additional practicing at all times. For this workshop, a laptop is optional; Windows Phone 7 devices will be provided for exercises.

Mobile devices are becoming the prevalent computing platform for most people. TouchDevelop is a new mobile development environment that enables anyone with a Windows Phone to create new apps directly on the smartphone, without a PC or a traditional keyboard. At the core is a new mobile programming language and editor that was designed with the touchscreen as the only input device in mind. Programs written in TouchDevelop can leverage all phone sensors such as GPS, cameras, accelerometer, gyroscope, and stored personal data such as contacts, songs, pictures. Thousands of programs have already been written and published with TouchDevelop.

Pex4Fun from Microsoft Research is a web-based serious gaming environment for teaching computer science. Pex4Fun can be used to teach and learn computer programming at many levels, from high school all the way through graduate courses. With Pex4Fun, a student edits code in any browser - with Intellisense - and Pex4Fun executes it and analyzes it in the cloud. Pex4Fun connects teachers, curriculum authors, and students in a unique social experience, tracking and streaming progress updates in real time. In particular, Pex4Fun finds interesting and unexpected input values that help students understand what their code is actually doing. The real fun starts with coding duels where students write code to implement a teacher's specification. Pex4Fun finds any discrepancies in behavior between the student's code and the specification. This tutorial equips participants with skills and knowledge of using Pex4Fun in teaching and learning, such as solving puzzles, solving coding duels, exploring course materials in feature courses, creating and teaching a course, creating and publishing coding duels, and learning advanced topics behind Pex4Fun.

An important goal of software testing is to achieve at least high structural coverage. To reduce the manual efforts of producing such high-covering test inputs, testers or developers can employ tools built based on automated structural test-generation approaches. Although these tools can easily achieve high structural coverage for simple programs, when they are applied on complex programs in practice, these tools face various problems, such as (1) the external-method-call problem (EMCP), where tools cannot deal with method calls to external libraries; (2) the object-creation problem (OCP), where tools fails to generate method-call sequences to produce desirable object states. Since these tools currently could not be powerful enough to deal with these problems in testing complex programs in practice, we propose cooperative developer testing, where developers provide guidance to help tools achieve higher structural coverage. To reduce the efforts of developers in providing guidance to tools, in this paper, we propose a novel approach, called Covana, which precisely identifies and reports problems that prevent the tools from achieving high structural coverage primarily by determining whether branch statements containing notcovered branches have data dependencies on problem candidates. We provide two techniques to instantiate Covana to identify EMCPs and OCPs. Finally, we conduct evaluations on two open source projects to show the effectiveness of Covana in identifying EMCPs and OCPs.

Achieving high structural coverage is an important goal of software testing. Instead of manually producing test inputs that achieve high structural coverage, testers or developers can employ tools built based on automated test-generation approaches, such as Pex, to automatically generate such test inputs. Although these tools can easily generate test inputs that achieve high structural coverage for simple programs, when applied on complex programs in practice, these tools face various problems, such as the problems of dealing with method calls to external libraries or generating method-call sequences to produce desired object states. Since these tools are currently not powerful enough to deal with these various problems in testing complex programs, we propose cooperative developer testing, where developers provide guidance to help tools achieve higher structural coverage. In this demo, we present Covana, a tool that precisely identifies and reports problems that prevent Pex from achieving high structural coverage. Covana identifies problems primarily by determining whether branch statements containing not-covered branches have data dependencies on problem candidates.

Software programs evolve throughout their lifetime undergoing various changes. While making these changes, software developers may introduce regression faults. It is desirable to detect these faults as quickly as possible to reduce the cost involved in fixing them. One existing solution is continuous testing, which runs an existing test suite to quickly find regression faults as soon as code changes are saved. However, the effectiveness of continuous testing depends on the capability of the existing test suite for finding behavioral differences across versions.

High-coverage testing is challenging. Modern object-oriented programs present additional challenges for testing. One key difficulty is the generation of proper method sequences to construct desired objects as method parameters. In this paper, we cast the problem as an instance of program synthesis that automatically generates candidate programs to satisfy a user-specified intent. In our setting, candidate programs are method sequences, and desired object states specify an intent. Automatic generation of desired method sequences is difficult due to its large search space---sequences often involve methods from multiple classes and require specific primitive values. This paper introduces a novel approach, called Seeker, to intelligently navigate the large search space. Seeker synergistically combines static and dynamic analyses: (1) dynamic analysis generates method sequences to cover branches; (2) static analysis uses dynamic analysis information for not-covered branches to generate candidate sequences; and (3) dynamic analysis explores and eliminates statically generated sequences. For evaluation, we have implemented Seeker and demonstrate its effectiveness on four subject applications totalling 28K LOC. We show that Seeker achieves higher branch coverage and def-use coverage than existing state-of-the-art approaches. We also show that Seeker detects 34 new defects missed by existing tools.

Unit testing has been widely recognized as an important and valuable means of improving software reliability, as it exposes bugs early in the software development life cycle. However, manual unit testing is often tedious and insufficient. Testing tools can be used to enable economical use of resources by reducing manual effort. Recently parameterized unit testing has emerged as a very promising and effective methodology to allow the separation of two testing concerns or tasks: the specification of external, black-box behavior (i.e., assertions or specifications) by developers and the generation and selection of internal, white-box test inputs (i.e., high-code-covering test inputs) by tools. A parameterized unit test (PUT) is simply a test method that takes parameters, calls the code under test, and states assertions. PUTs have been supported by various testing frameworks. Various open source and industrial testing tools also exist to generate test inputs for PUTs.

Test coverage criteria including boundary-value and logical coverage such as Modified Condition/Decision Coverage (MC/DC) have been increasingly used in safety-critical or mission-critical domains, complementing those more popularly used structural coverage criteria such as block or branch coverage. However, existing automated test-generation approaches often target at block or branch coverage for test generation and selection, and therefore do not support testing against boundary-value coverage or logical coverage. To address this issue, we propose a general approach that uses instrumentation to guide existing test-generation approaches to generate test inputs that achieve boundary-value and logical coverage for the program under test. Our preliminary evaluation shows that our approach effectively helps an approach based on Dynamic Symbolic Execution (DSE) to improve boundary-value and logical coverage of generated test inputs. The evaluation results show 30.5% maximum (23% average) increase in boundary-value coverage and 26% maximum (21.5% average) increase in logical coverage of the subject programs under test using our approach over without using our approach. In addition, our approach improves the fault-detection capability of generated test inputs by 12.5% maximum (11% average) compared to the test inputs generated without using our approach.

Mutation testing has been used to assess and improve the quality of test inputs. Generating test inputs to achieve high mutant-killing ratios is important in mutation testing. However, existing test-generation techniques do not provide effective support for killing mutants in mutation testing. In this paper, we propose a general test-generation approach, called PexMutator, for mutation testing using Dynamic Symbolic Execution (DSE), a recent effective test-generation technique. Based on a set of transformation rules, PexMutator transforms a program under test to an instrumented meta-program that contains mutant-killing constraints. Then PexMutator uses DSE to generate test inputs for the meta-program. The mutant-killing constraints introduced via instrumentation guide DSE to generate test inputs to kill mutants automatically. We have implemented our approach as an extension for Pex, an automatic structural testing tool developed at Microsoft Research. Our preliminary experimental study shows that our approach is able to strongly kill more than 80% of all the mutants for the five studied subjects. In addition, PexMutator is able to outperform Pex, a state-of-the-art test-generation tool, in terms of strong mutant killing while achieving the same block coverage.

Constraints in form regular expressions over strings are ubiquitous. They occur often in programming languages like Perl and C#, in SQL in form of LIKE expressions, and in web applications. Providing support for regular expression constraints in program analysis and testing has several useful applications. We introduce a method and a tool called Rex, for symbolically expressing and analyzing regular expression constraints. Rex is implemented using the SMT solver Z3, and we provide experimental evaluation of Rex.

Dynamic symbolic execution is a structural testing technique that systematically explores feasible paths of the program under test by running the program with different test inputs to improve code coverage. To address the space-explosion issue in path exploration, we propose a novel approach called Fitnex, a search strategy that uses state-dependent fitness values (computed through a fitness function) to guide path exploration. The fitness function measures how close an already discovered feasible path is to a particular test target (e.g., covering a not-yet-covered branch). Our new fitness-guided search strategy is integrated with other strategies that are effective for exploration problems where the fitness heuristic fails. We implemented the new approach in Pex, an automated structural testing tool developed at Microsoft Research. We evaluated our new approach by comparing it with existing search strategies. The empirical results show that our approach is effective since it consistently achieves high code coverage faster than existing search strategies.

Test coverage such as branch coverage is commonly measured to assess the sufficiency of test inputs. To reduce tedious manual efforts in generating high-covering test inputs, various automated techniques have been proposed. Some recent effective techniques include Dynamic Symbolic Execution (DSE) based on path exploration. However, these existing DSE techniques cannot generate high-covering test inputs for programs using complex regular expressions due to large exploration space; these complex regular expressions are commonly used for input validation and information extraction. To address this issue, we propose an approach, named Reggae, to reduce the exploration space of DSE in test generation. In our evaluation, we apply Reggae on various input-validation programs that use complex regular expressions. Empirical results show that Reggae helps a test-generation tool generate test inputs to achieve 79% branch coverage of validators, improved from 29% achieved without the help of Reggae.

An objective of unit testing is to achieve high structural coverage of the code under test. Achieving high structural overage of object-oriented code requires desirable method-call sequences that create and mutate objects. These sequences help generate target object states such as argument or receiver object states (in short as target states) of a method under test. Automatic generation of sequences for achieving target states is often challenging due to a large search space of possible sequences. On the other hand, code bases using object types (such as receiver or argument object types) include sequences that can be used to assist automatic test-generation approaches in achieving target states. In this paper, we propose a novel approach, called MSeqGen, that mines code bases and extracts sequences related to receiver or argument object types of a method under test. Our approach uses these extracted sequences to enhance two state-of-the-art test-generation approaches: random testing and dynamic symbolic execution. We conduct two evaluations to show the effectiveness of our approach. Using sequences extracted by our approach, we show that a random testing approach achieves 8.7% (with a maximum of 20.0% for one namespace) higher branch coverage and a dynamic-symbolic-execution-based approach achieves 17.4% (with a maximum of 22.5% for one namespace) higher branch coverage than without using our approach. Such an improvement is significant as the branches that are not covered by these state-of-the-art approaches are generally quite difficult to cover.