Gender Equality in Software Engineering

three extracts from an international workshop 

By:  Jeffrey Carver (@JeffCarver32) and Alexander Serebrenik (@aserebrenik)

Associate Editor: Xabier Larrucea (@xlarrucea)

This post diverges from the standard way of publishing because it links to the current issue of the IEEE Software magazine  (here). This approach helps readers to compliment magazine issues with related posts.

In fact, the following summaries are stemming from the 2nd International Workshop on Gender Equality in Software Engineering

“Characterizing Women (Not) Contributing to Open-Source” by Wurzelová and colleagues studies factors related to women’s under-representation in open-source software development. Using the results from the 2018 Stack Overflow survey of software developers (100,000 respondents, 3,436 women), the authors compare the characteristics of women who reported contributions to open-source software development with the characteristics of women who did not report contributions to open-source software. The characteristics the authors analyzed include: experience, age, education, perceived competence, feelings of kinship and competition, and self-education activities. Surprisingly, the authors did not identify any marked differences in any of these characteristics. This result suggests, among the survey respondents, the population of women who reported contributions to open-source software development is similar to the population of women who do not report contributions to open-source development. Especially surprising is that the authors did not identify any difference in the respondents’ perception of their own competence, even though underestimating one’s own competence is widely considered a reason for why women contribute less in open-source environments. This result hints at the presence of other reasons, not analyzed in this study, why the participation of women is lower in open-source software. This paper appears in the 2019 GE workshop. Access it at http://bit.ly/PD-2019-Blog-01. 

“Women-only Spaces of Open Source”, by Singh studies the phenomenon that several open-source projects have designated women-centered spaces to facilitate the interactions of women, increase their participation, and empower them. The author observed that among 355 established open-source projects listed on Wikipedia, only 16 had such spaces. The type of space varied from Facebook/Twitter entities to individual blog posts to entire websites dedicated to supporting women involved in the project. The oldest women-centered space, LinuxChix, is almost twenty years old. The most recent one, Women in Bitcoin, goes back to 2013. All the spaces implement strategies to encourage the involvement of women by showcasing their achievements, pairing more and less experienced participants, and support the participants in revealing their identity if they desire to do so. The research suggests that these women-centered spaces fill a gap in the infrastructure of open source projects and have implications for improving the overall underrepresentation of women in technology. However, further research is required to understand why some of these spaces become inactive or cease to exist while other flourish. This paper appears in the 2019 GE workshop. Access it at http://bit.ly/PD-2019-Blog-02.  

“How Remote Work can Foster a More Inclusive Environment for Transgender Developers” by Ford and colleagues studies the experience of transgender software developers. By talking to several transgender software developers the authors identified three themes that resonate across the trans experience and intersect with the advantages to working in software development remotely: identity disclosure, high-impact technical work, and the autonomy to disengage and re-engage. Based on these interviews and survey of the literature, the authors  hypothesize that remote work technologies can increase the sense of empowerment transgender people have to be authentic and effective in their work. This paper appears in the 2019 GE workshop. Access it at http://bit.ly/PD-2019-Blog-03. 

Communicating Stakeholders’ needs with Vision Videos

Communicating Stakeholders’ needs

Vision Videos to Disclose, Discuss, and Align Mental Models for Shared Understanding

By: Oliver Karras (@KarrasOliver)

Associate Editor: Muneera Bano (@DrMuneeraBano)

One central task in requirements engineering (RE) is to understand, document, and convey the needs of diverse stakeholders among all parties involved. The process of coordinating and communicating these needs so that the development team can implement a solution that the stakeholders accept is called requirements communication. Requirements communication involves developing and negotiating a shared understanding of the goals, plans, status, and context of a project among all project partners, which requires disclosing, discussing, and aligning their mental models of the future system, i.e. their visions. A mental model is a conceptual idea in the mind of a person that represents the person’s individual understanding of how a system will work. Shared understanding leads to a common vision that summarizes the essence of the mental models of all stakeholders of the ultimate system that satisfies their needs. This common vision, in turn, describes the boundary of the system and thus its scope. Therefore, shared understanding is one of the most important objectives in RE since it enables the stakeholders and development team to assess and agree on what the relevant requirements are and what the meaning of these requirements is regarding the future system.

The Challenge of Establishing a Common Vision

Stakeholders and the development team can achieve shared understanding more easily if they use practices that support proactive information exchange among them. However, current RE practices mainly describe a vision as text. This representation is less suited for communication with a proactive information exchange due to two main reasons. First, the inherent restrictions of natural language such as ambiguity and abstraction increase the likelihood of undetected misunderstandings that limit shared understanding. Second, textual documentation cannot capture all information that is relevant to stakeholders and the development team. Mental models are difficult to capture since they are intangible due to their tacit representations in the persons’ minds. Thus, mental models require other communication mechanisms that are more suited for proactive information exchange to disclose, discuss, and align them to establish a common vision and thus shared understanding.

Vision Videos for Shared Understanding

In contrast to text, video is a more promising communication mechanism for shared understanding when representing a vision. Such a video, so-called vision video, visualize a vision of a future system, i.e., the video producer’s mental model. This visualization discloses the mental model by externalizing the model and thus making it tangible. However, even this external representation does not encapsulate shared understanding but merely aids to develop shared understanding. The explicit representation provides a reference point for the active discussion among the parties involved to align their mental models. The desired result of a common vision can be more easily achieved since critical issues of the mental models are identified, discussed, understood, and, at best resolved by making them explicit and obvious. The established common vision, in turn, reduces the risk of misunderstandings due to false assumptions.

Vision video A vision video is a video that represents a vision or parts of it for achieving shared understanding among all parties involved by disclosing, discussing, and aligning their mental models of the future system.

Current Research on Vision Videos

Vision videos are no new practice. One well-known example of a vision video is Apple’s Knowledge Navigator (1987). Since 2017, the YouTube channel “EU Science and Innovation” provides a playlist of vision videos of research and innovation projects funded by the European Union. These videos highlight the future impact of the projects on the life of Europe’s citizens and society as a whole.

Despite the benefits of vision videos, videos are not an established communication mechanism for shared understanding. In a survey, I investigated the obstacles that prevent software professional from producing and using videos in RE. In particular, I found that software professionals (1) perceive the effort of producing and using videos in RE as too high; and (2) lack knowledge about how to produce good videos. Based on these findings, I currently work on an affordable video approach that enables software professionals to produce and use vision videos for shared understanding at moderate costs and sufficient quality. This approach consists of two concepts. First, I work on including videos as a by-product of established RE practices and techniques, such as prototyping and workshops, to reduce the production effort. Second, I am working on a quality model for vision videos to guide video production by software professionals. This quality model will offer a basis for software professionals to estimate the consequent effort and activities to produce a good vision video. I believe that these two concepts can help to integrate vision videos in RE to support effective requirements communication with a proactive information exchange for establishing a shared understanding among all parties involved.

Female Farmers' Values-Based Apps

Can a Software Reflect Values of Under-represented Users?

Author: Rifat Ara Shams (@swarna601)

Associate Editor: Muneera Bano (@DrMuneeraBano)

Software is ubiquitous in all aspects of daily life, therefore it gives rise to the need to account for human values in software. However, existing Software Engineering (SE) techniques have paid less attention to deal with the human values which are reflected frequently in incidents of value breaches. A recent example of the value breach of software was the news, “Instagram removes ad company after data grab” that got huge media coverage. Similarly, there are various other examples such as the collapse of Facebook's share price due to Cambridge Analytica scandal, resignation of Volkswagen CEO, a 30% drop in the company’s stock price and a 25% drop in sales within a year for the recent issue of installing a deceptively designed software to fool fuel emission tests in Volkswagen emissions fiasco. There are also a few incidents reported about value breaches in mobile apps. For example, a ride-sharing app in Bangladesh named Pathao accessed its users’ contact lists and SMS without taking their permission for a business purpose. As a result, Pathao had to face humiliation and loss of profit which resulted in sacking 300 employees within a day without any prior notice. These value breaches cause users’ dissatisfaction and contribute to negative socio-economic impacts.

Human values are getting less attention from the software engineering research community. In our research, we classified 1350 papers at four top-tier SE journals and conferences (ICSE, FSE, TOSEM and TSE) from 2015-2018 to investigate the prevalence of human values in SE and found that only 16% (216) of the papers are directly relevant to human values [1]. There is a need to understand what human values are and how they can be incorporated into the software.

What are Human Values?

According to literature, values have “importance to you, as guiding principles in your life”. Values are the reflection of people’s personal and social preferences [2]. Social scientists have been researching basic human values to conceptualize those since 1950 [3].

In our research, we used Schwartz theory, which is the highly cited and widely applied classification, not just in the social sciences but also in other disciplines. In 1992, Schwartz divided values into ten main categories based on their motivational goals and 58 value items by which the main values are measured as shown in Figure 1. Values located close to each other are congruent and further apart are opposite in nature [4].

How to Consider Values in Software?

The first step to consider human values in software is awareness. Though the importance of including human values in software is significant, it is largely ignored in software engineering due to the lack of a clear definition [5]. This necessitates a concrete definition of human values in SE. Furthermore, there is a need for proper guidelines, tools, and techniques for integrating human values in SE.

Case Study in Bangladesh

We are conducting a case study with the marginalized people in rural Bangladesh with the aim to ensure sustainable use of technology. We are currently exploring the values of female farmers in rural Bangladesh and to what extent the existing agriculture apps reflect their values. To discover their values, we will utilise a well-known value measurement instrument proposed by Schwartz, Portrait Values Questionnaire (PVQ) [4]. In this method, short text portraits of different people, gender-matched with the respondents, are created. Each portrait describes a person’s goals, aspirations and wishes that implicitly reflect the importance of value for that person. We believe, there is a potential in this research to create awareness in SE researcher to consider human values and to provide a reference point to replicate or repeat similar relevant research in collaboration with practitioners and other community stakeholders.

References:

[1] Perera, H., Nurwidyantoro, A., Hussain, W., Mougouei, D., Whittle, J., Shams, R. A., & Oliver, G. (2019). A Study on the Prevalence of Human Values in Software Engineering Publications, 2015-2018. arXiv preprint arXiv:1907.07874.

[2] Milton Rokeach. The nature of human values. Free press, 1973.

[3] Shalom H Schwartz. Basic human values:  Theory, methods, and application. Risorsa Uomo, 2007.

[4] Shalom  H Schwartz.   An overview of  the schwartz theory  of basic values. Online  readings in Psychology and Culture, 2(1):11, 2012.

[5] Davoud Mougouei, Harsha Perera, Waqar Hussain, Rifat Shams, and Jon Whittle. Operationalizing human values in software: a research roadmap. In Proceedings of the 2018 26th ACM Joint Meeting on  European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 780–784. ACM, 2018.

Where to deploy my API? From Server-Centric to Client-Centric Architectural Styles.

Authors: Javier Berrocal (@jberolm), Jose Garcia-Alonso (@jmgaralo), Juan Manuel Murillo (@juanmamuro)

 Associate Editor:Niko Mäkitalo (@nikkis)

The increase in the capabilities of near-to-the-edge and end devices has allowed developers to take these devices as a possible destination for the deployment architecture of any API. They can better satisfy the essential requirements of some APIs, such as responsiveness, location-awareness, etc., but they also present some restrictions regarding resource consumption (battery, data traffic, and so on). Currently, developers have to analyze every architectural style carefully and available device to meet the system requirements better. Different tools and proposals are available to facilitate both the decision-making process and the application of the selected architecture.

Increase in the capabilities of near-to-the-end devices

During the last few years, the predominant architectural style for the deployment of APIs has been the Server-Centric or Cloud-Centric style. In these styles, the most demanding features, like storing or computing of the managed data, are offloaded to cloud environments. These styles provide improved scalability, fault tolerance, and greater control of the operational costs. They allowed developers to implement applications with an excellent response time that can be visualized and used from end devices, that until a few years ago had very limited capabilities.

In the last few years, end devices and near-to-the-edge devices capabilities have increased tremendously. Their storage and computational capabilities have increased in order to be able to execute more complex tasks. This allowed researchers to develop new paradigms, such as Fog, Mist or Edge Computing, in which the whole or part of an application or API is loaded in end devices or near-to-the-edge devices, reducing the network load and the dependency of the cloud environment and improving response time. For instance, by using data closer to, or even inside, the targeted device.

Therefore, developers not only have to make decisions about how to develop a specific API but also what architectural style to apply and where each microservice should be deployed to meet the system requirements better. Initially, one may think that the behaviors implemented with one style, cannot be achieved with others. Our experience, however, has shown us that similar behaviors can be obtained with any of them.

Trade-off among capabilities and limitations

Therefore, just at the moment in which the developer has to select what architectural and deployment style to use, s/he has to do a complex trade-off among the system requirements, and the capabilities and limitations of the different devices in the environment. Deploying an API following a server-centric style could increase the system scalability or the fault tolerance, but could also negatively affect the operational cost, location-awareness, and responsiveness.  Deploying an API in near-to-the edge devices could positively impact these requirements, but they also present some significant limitations. For instance, a constraining factor of these devices is the resource consumption (battery, data traffic, etc.). Many of these devices, such as mobile phones, smart speakers, etc. are battery-powered. Likewise, some of them have to interact using the mobile network, either because they are mobile or because of their specific situation, which entails the consumption of the data plan.  In the deployment of any API, the correct management of these resources is crucial for user satisfaction. It is well known that resource consumption, is a factor determining the application success.

Therefore, all these dimensions have to be taken into account to select the architectural style that best fit the system requirements, doing a trade-off among the capabilities and limitations of every connected device and the system requirements. 

Tools helping in the decision-making process

During the last few years, researchers have been working on defining methods for measuring whether the requirements are met, from those directly related to the system behavior to those that impact on other non-functional dimensions such as the resource consumption. 

Some works both in the academia and in the industry domains are focused on analyzing the final developed and deployed an application for identifying if those requirements are met. For instance, Giovani et al. presented some years ago, a monitoring framework able to adjust the resources assigned to the deployed application or to face transient failures replicating and restarting components to provide resiliency. Leitner et al. proposed a tool to re-evaluate the cost of an application in the background continually. Alternatively, for end Android devices, Batterystatscould be used to collects battery data about the consumption of a specific application.

Another proposal, however, is focused on evaluating during the early stages of the development process how these requirements can be met, helping in the decision-making process of which architectural design are the most suitable. For instance, some works propose a different heuristic to identify where the microservices should be deployed to meet some requirements such as responsiveness better. Likewise, the authors of this post have been working on defining a conceptual framework to identify in early development stages what architectural style is the most appropriate to achieve a reduction in terms of resource consumption.

Generating microservices for different architectures

Once identified the most appropriate style for achieving the system requirements, the API has to be developed and deployed.

Currently, the specification and development of microservices are supported by a large number of tools that facilitate the work of the developer. Specifications such as OpenAPI, are widely used to detail an API, generate the documentation, perform tests and, even, generate the API skeleton. This type of tools can even generate the source code for different technologies such as Node.JS, Kotlin, JAX-RS,etc., but they are focused on deploying the API in a server or a cloud environment. 

Fewer commercial tools are supporting other architectural styles, such as client-centric or others architectures based on fog or mist computing. However, at the research level, more and more proposals are presented detailing how to use these specifications to generate the skeleton and to deploy microservices in other elements of the network. For instance, Noura et al. propose WoTDL2API tool, that automatically generates a running RESTful API based on the OpenAPI specification and its code generation toolchain to control different IoT devices. The generated source code can be deployed in near-to-the-edge devices, such as gateways, routers, and so on. 

Likewise, the authors of this post have recently proposed a set of tools to generate and deploy a running RESTful API based on the OpenAPI standard on end devices such as smartphones, IoT devices, etc., providing support to client-centric architectures. 

Summarizing

APIs and microservices until now have been designed and developed to be deployed on a cloud environment because of its computing capabilities, fault tolerance, responsiveness, etc. Nevertheless, the ever-increasing capabilities of other elements in the networks have fostered the deployment of these APIs in these devices to better meet some requirements such as scalability, interoperability, real-time responsiveness, security, or location-awareness.

Nevertheless, for developers to apply the best architectural style, first, they need tools helping in the decision making process by providing information for each style on the degree of compliance of the requirements; and, secondly, tools supporting and reducing the effort required to develop and deploy the microservices for each architectural style are needed. If these tools are not provided developer, tend to use only known architectures and those with greater support.

Studying human values in software engineering

Authors: Emily Winter and Maria Angela Ferrario
Associate Editor: Jinghui Cheng (@JinghuiCheng)

The Values in Computing (ViC) project: http://www.valuesincomputing.org

Why do human values matter for software engineering? Recent years have seen high profile software scandals and malpractices, in which individual privacy and social democracy have been undermined, as in the case of Cambridge Analytica’s use of Facebook data [1] and even human lives lost, as in the case of Boeing 737 [2]. As another recent IEEE Software post puts it, we are heading into an age of considerable ‘values debt’ [3], as the negative societal consequences, both intended and unintended, of our software systems mount up.

There is a pressing need then to understand how human values operate, to develop methods and tools to study them in a software engineering context, and to build on this understanding to consider how SE research might contribute to a more socially responsible software industry.

How do values operate?

We use values research from social psychology as our framework. In particularly, we draw on Schwartz’s values model, based on extensive empirical research spanning the last three decades. Schwartz’s work has identified, through survey research, a range of values that are recognised across cultures and that operate relationally. Schwartz’s values model operates across two key oppositional axes: self-enhancement vs. self-transcendence; and openness vs. conservation [4].

We also use Maio’s work, which considers values as mental constructs that can be studied at three different levels: the system level (the relationships outlined by Schwartz); the personal level (the different interpretations of values held by individuals); and the instantiation level (how values are expressed through behaviours) [5]. At the system level, for example, a software engineer who is highly concerned about their personal career development (achievement) is – according to Schwartz’s model – less likely to be concerned about the environmental sustainability (universalism) of the systems they are building. At the personal level, software engineers may have different interpretations of high quality code (achievement) - e.g. ‘code that does the job’ vs. ‘elegant code’. At the instantiation level, a concern with privacy may manifest in a development decision not to track user queries.

Understanding values in software engineering

In order to study human values in a software engineering context, we required methods that were relatable and relevant to the software engineering community. We used Q-methodology as our starting point [6]. Q-methodology is a well-established method designed to systematically study subjectivity. It involves participants taking part in a card ranking exercise; they are interviewed about their decisions and multiple participants’ ‘sorts’ can be statistically analysed. The structured nature of the sorting helped with the systematic articulation and analysis of the qualitative data elicited from participant’s narratives; it was also important that the card statements were specific to the software engineering community. We used the newly revised ACM Code of Ethics [7] as a basis, choosing principles that corresponded with Schwartz’s values types and filling in any gaps by creating statements in accordance with the missing values. It was important, in order to gain a full understanding of the software engineering context, to consider a wide range of values, not just those considered ethical, in order to understand fully values trade-offs within complex industry contexts. Power and profit were as important for our study as honesty and the social good.

The role of the researcher in promoting a socially responsible software industry

One of our key findings is that people interpret and act out values in very different ways. Two of our study participants, for example, who both placed the statement ‘it is important for me that the public good is the central concern of all professional computing work’ in their ‘top 3’, showed almost opposite understandings of this value. For Laura, for example, the public good was about optimising the user experience: she explained they would ‘analyse the data once the user hits our website; we would then optimise off that behaviour’. By contrast, Stuart didn’t want to overly ‘structure’ the experience of users. He explained that an e-commerce site could ask users ‘do you want us to try and automate your offers? Yes or no’. He viewed an overly structured web experience as being oppositional to users’ freedom of choice.

By simply introducing the Q-Sort to software engineers, we have already encouraged articulation of these differences of interpretation, things that are often taken for granted and rarely explained. Maio and Olson, for example, argue that values often act as truisms, ‘widely shared, rarely questioned, and, therefore, relatively bereft of cognitive support’ [8]. Carrying out this kind of research may be the first step in encouraging a more values-aware and values-reflective technology industry – in which the taken-for granted may begin to be reflected upon and articulated. Avenues for future work include identifying opportunities for light-weight interventions that enable values reflection as an integral part of the agile process, for example.

As well as encouraging discussion of values within industry, we (SE researchers and academics) need to foster reflective, critical skills within our students. For example, we used the Q-Sort as a teaching tool in our Software Studio, a 20-week long module for second year Software Engineering undergraduate students. Within this module, students work in small teams to ideate, design and develop a software application. We introduced the Q-Sort to teams early on in the process as a way of encouraging values articulation and prioritisation that would underpin the entire software engineering decision making process. As well as generating discussion, reflection and critical thinking, this led to concrete future design decisions. One team, for example, went on to adopt a ‘most-vulnerable-first’ approach to system design and development for their train journey planning app, prioritizing search needs for people with disabilities, people with young children, and the elderly. In contrast to standalone ethics courses, the Software Studio embedded values and ethical considerations into the module; they were integrated with technical skills, not an optional add-on.

This is one example of teaching practice that supports the Values in Computing mission: that the next generation of computing professionals will be equipped with the technical tools, foundational knowledge, and critical skills necessary to distinguish responsible software engineering decisions from those that are potentially harmful to self and society.

References

1. The Guardian, Cambridge Analytica Files. Retrieved on 12 August 2019 from https://www.theguardian.com/news/series/cambridge-analytica-files
2. Helmore, E. (2019) ‘Profit over safety? Boeing under fire over 737 Max crashes as families demand answers’, The Guardian. Retrieved on 12 August 2019 from https://www.theguardian.com/business/2019/jun/17/boeing-737-max-ethiopian-airlines-crash
3. Hussain, W. (2019) ‘Values debt is eating software’, IEEE Software blog. Retrieved on 12 August 2019 from http://blog.ieeesoftware.org/2019/07/values-debt-is-eating-software.html
4. Schwartz, S. H. et al. (2012) ‘Refining the theory of basic individual values’. Journal of personality and social psychology 103(4): 663-688
5. Maio, G. R. (2010) ‘Mental representations of social values’. in Advances in Experimental Social Psychology (Vol 42). Academic Press, pp. 1–43.
6. Winter, E. et al. (2019) ‘Advancing the study of human values in software engineering’. In Proceedings of the 12^thInternational Workshop on Cooperative and Human Aspects of Software Engineering (CHASE '19). IEEE Press, pp. 19-26. 
7. ACM (2019) Code of Ethics and Professional Conduct. Retrieved on 12 August 2019 from https://www.acm.org/code-of-ethics
8. Maio, G. R. and J. M. Olson (1998) ‘Values as truisms: Evidence and implications’. Journal of Personality and Social Psychology, 74(2): 294-311.

Design and Evolution of C-Reduce (Part 2)

Author: John Regehr (@johnregehr)

Associate Editor: Karim Ali (@karimhamdanali)

Part 1 of this series introduced C-Reduce and showed how it combines a domain-independent core with a large collection of domain-specific passes in order to create a highly effective test-case reducer for C and C++ code. This part tells the rest of the story and concludes.

Parallel Test-Case Reduction

C-Reduce's second research contribution is to perform test-case reduction in parallel using multiple cores. The parallelization strategy, based on the observation that most variants are

uninteresting, is to speculate along the uninteresting branch of the search tree. Whenever C-Reduce discovers an interesting variant, all outstanding interestingness tests are killed and a new line of speculation is launched. This is the same approach that was subsequently rediscovered by the creator of halfempty.

C-Reduce has a policy choice between taking the first interesting variant returned by any CPU, which provides a bit of extra speedup but makes parallel reduction non-deterministic, or only taking an interesting variant when all interestingness tests earlier in the search tree have reported that their variants are uninteresting. We tested both alternatives and found that the speedup due to non-deterministic choice of variants was minor. Therefore, C-Reduce currently employs the second option, which always follows the same path through the search tree that non-parallel C-Reduce would take. The observed speedup due to parallel C-Reduce is variable, and is highest when the interestingness test is relatively slow. Speedups of 2–3x vs. sequential reduction are common in practice.

Applicability and Moving Towards Domain-Independence

Something that surprised us is how broadly applicable C-Reduce is to test cases in languages other than C and C++. Our users have found it effective in reducing Java, Rust, Julia, Haskell, Racket, Python, SMT-LIB, and a number of other languages. When used in this mode, the highly C/C++-specific C-Reduce passes provide no benefit, but since they fail quickly they don't do much harm. (C-Reduce also has a --not-c command line option that avoids running these passes in the first place.) One might ask why C-Reduce is able to produce good results for languages other than C and C++; the answer appears to be based on the common structural elements found across programming languages in the Algol and Lisp families. In contrast, in our limited experience, C-Reduce does a very poor job reducing test cases in binary formats such as PDF and JPEG. Other reducers, such as the afl-tmin tool that ships with afl-fuzz, work well for binary test cases.

A consequence of the modular structure of C-Reduce is that while its transformation passes are aimed at reducing C and C++ code, the C-Reduce core is completely domain-independent. C-Reduce has been forked to create a highly effective reducer for OpenCL programs. We believe it would be relatively straightforward to do something similar for almost any other programming language simply by tailoring the passes that C-Reduce uses.

Limitations

When used for its intended purpose, when does C-Reduce work badly? We have seen two main classes of failure. First, C-Reduce can be annoyingly slow. This typically happens when the passes early in the phase ordering, which are intended to remove a lot of code quickly, fail to do this. Second, highly templated C++ sometimes forces C-Reduce to terminate with an unacceptably large (say, >1 KB) final result. Of course this is better than nothing, and subsequent manual reduction is usually not too difficult, but it is frustrating to have written 69 different Clang-based passes and to still find effectively irreducible elements in test cases. The only solution—as far as we know—is to strengthen our existing transformation passes and to create more such passes.

A small minority of compiler bugs appears to be impossible to trigger using small test cases. These bugs are exceptions to the small scope hypothesis. They typically stem from resource-full bugs in the compiler. For example, a bug in register spilling code requires the test case to use enough registers that spilling is triggered; a bug in logic for emitting long-offset jumps requires the test case to contain enough code that a long offset is required; etc. These test cases are just difficult to work with, and it is not clear to us that there's anything we can do to make it easier to debug the issues that they trigger.

C-Reduce Design Principles

In summary, C-Reduce was designed and implemented according to the following principles:

1. Be aggressive: make the final reduced test case as small as possible.
2. Make the reducer fast, for example using parallelism, careful phase ordering of passes, and avoiding unnecessary I/O traffic, when this can be done without compromising the quality of the final output.
3. Make it as easy as possible to implement new passes, so that many domain-specific passes can be created.
   
   
4. Keep the C-Reduce core domain-independent.
5. Focus only on producing potentially-interesting variants, delegating all other criteria to the user-supplied interestingness test.

Directions for Future Test-Case Reduction Research

Although perhaps a few dozen papers have been written about test-case reduction since Hildebrandt and Zeller's initial paper 19 years ago, I believe that this area is under-studied relative to its practical importance. I'll wrap up this article with a collection of research questions suggested by our experience in over a decade of work on creating a highly aggressive reducer for C and C++.

What is the role of domain-specificity in test case reduction? Researchers who cite C-Reduce appear to enjoy pointing out that it is highly domain-specific (nobody seems to notice that the C-Reduce core is domain-independent, and that the pass schedule is easy to modify). The implication is that domain-specific hacks are undesirable and, of course, an argument against such hacks would be forceful if backed up by a test-case reducer that produced smaller final C and C++ code than C-Reduce does, without using domain knowledge. So far, such an argument has not been made.

Is domain knowledge necessary, or can a domain-independent test-case reducer beat C-Reduce at its own game? The most impressive such effort that we are aware of is David MacIver's structureshrink, which uses relatively expensive search techniques to infer structural elements of test cases that can be used to create variants. Anecdotally, we have seen structureshrink produce reduced versions of C++ files that are smaller than we would have guessed was possible without using domain knowledge. Even so, some useful transformations such as function inlining and partial template instantiation seem likely to remain out-of-reach of domain-independent reduction techniques.

What is the role of non-greedy search in test-case reduction? In many cases, the order in which C-Reduce runs its passes has little or no effect on the final, reduced test case. In other words, the search is often diamond-shaped, terminating at the same point regardless of the path taken through the search space. On the other hand, this is not always the case, and when the search is not diamond-shaped, a greedy algorithm like C-Reduce's risks getting stopped at a local minimum that is worse than some other, reachable minimum. The research question is how to get the benefit of non-greedy search algorithms without making test-case reduction too much slower.

What other parallelization methods are there? C-Reduce's parallelization strategy is simple, gives a modest speedup in practice, and always returns the same result as sequential reduction. There must be other parallel test-case reduction strategies that hit other useful points in the design space. This is, of course, related to the previous research question. That is, if certain branches in the search tree can be identified as being worth exploring in both directions, this could be done in parallel.

What is the role of canonicalization in test-case reduction? A perfectly canonicalizing reducer would reduce every program triggering a given bug to the same final test case. This is a very difficult goal, but there are many relatively simple strategies that can be employed to increase the degree of canonicalization, such as putting arithmetic expressions into a canonical form, assigning canonical names to identifiers, etc. C-Reduce has a number of transformations that are aimed at canonicalization rather than reduction. For example, the reduced test case at the top of Part 1 of this piece has four variables a, b, c, and d, which first appear in that order. I believe that more work in this direction would be useful.

Can we avoid bug hijacking? Test reduction sometimes goes awry when the bug targeted by the reduction is "hijacked" by a different bug. In other words, the reduced test case triggers a different bug than the one triggered by the original. During a compiler fuzzing campaign this may not matter since one fuzzer-generated bug is as good as another, but hijacking can be a problem when the original bug is, for example, blocking compilation of an application of interest. Hijacking is particularly common when the interestingness test looks for a non-specific behavior such as a null pointer dereference. C-Reduce pushes the problem of avoiding hijacking onto the user who can, for example, add code to the interestingness test looking for specific elements in a stack trace. The research question here is whether there are better, more automated ways to prevent bug hijacking.

Obtaining C-Reduce

Binary C-Reduce packages are available as part of many software distributions including Ubuntu, Fedora, FreeBSD, OpenBSD, MacPorts, and Homebrew. Source code can be found at:

https://github.com/csmith-project/creduce

Acknowledgments: C-Reduce was initially my own project, but by lines of code the largest contributor by a factor of two is my former student Yang Chen, now a software engineer at Microsoft. Yang wrote effectively all of the Clang-based source-to-source transformation code, more than 50,000 lines in total. Eric Eide, a research professor in computer science at the University of Utah, is the other major C-Reduce contributor. Our colleagues Pascal Cuoq, Chucky Ellison, and Xuejun Yang also contributed to the project, and we have gratefully received patches from a number of external contributors. Someone created a fun visualization of the part of C-Reduce's history that happened on Github:

Finally, I’d like to thank Eric Eide and Yang Chen for reviewing and suggesting improvements to this piece.