Interesting Research

Date
Tags research
Target Audience Computer science people.

Sources

Events

Mailing lists

Topics

Sys­tem­atic con­cur­rency testing (SCT)

De­term­in­istic testing for con­cur­rent pro­grams, by con­trolling the scheduling de­cisions made to in­tel­li­gently ex­plore the state space. Can be com­plete or in­com­plete. Draws from model checking and pro­gram veri­fic­a­tion.

Pa­pers

  • Par­tial-Order Methods for the Veri­fic­a­tion of Con­cur­rent Sys­tems: An Ap­proach to the State-­Ex­plo­sion Problem (ps)
    Patrice Gode­froid.
    PhD thesis, 1996.

  • Dy­namic par­tial-order re­duc­tion for model checking soft­ware (pdf)
    Cormac Flanagan and Patrice Gode­froid.
    In Sym­posium on Prin­ciples of Pro­gram­ming Lan­guages (POPL). 2005.

  • It­er­ative Con­text Bounding for Sys­tem­atic Testing of Mul­ti­th­readed Pro­grams (pdf)
    Madanlal Musuvathi and Shaz Qadeer.
    In Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI). 2007.

  • Ef­fective Random Testing of Con­cur­rent Pro­grams (pdf)
    Koushik Sen.
    In In­ter­na­tional Con­fer­ence on Auto­mated Soft­ware En­gin­eering (ASE). 2007.

  • Fair State­less Model Checking (pdf)
    Madanlal Musuvathi and Shaz Qadeer.
    In Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI). 2008.

  • Race Dir­ected Random Testing of Con­cur­rent Pro­grams (pdf)
    Koushik Sen.
    In Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI). 2008.

  • A Ran­dom­ized Sched­uler with Prob­ab­il­istic Guar­an­tees of Finding Bugs (pdf)
    Se­bastian Burck­hardt, Pravesh Kothari, Madanlal Musuvathi, and San­tosh Nagarakatte.
    In In­ter­na­tional Con­fer­ence on Ar­chi­tec­tural Sup­port for Pro­gram­ming Lan­guages and Op­er­ating Sys­tems (AS­PLOS). 2010.

  • Delay-bounded Scheduling (pdf)
    Mi­chael Emmi, Shaz Qadeer, and Zvon­imir Rakamaric.
    In Sym­posium on Prin­ciples of Pro­gram­ming Lan­guages (POPL). 2011.

  • Bounded Par­tial-order Re­duc­tion (pdf)
    Kath­erine E. Coons, Madan Musuvathi, and Kathryn S. McKin­ley.
    In In­ter­na­tional Con­fer­ence on Ob­ject Ori­ented Pro­gram­ming Sys­tems, Lan­guages & Ap­plic­a­tions (OOPSLA). 2013.

  • CON­CUR­RIT: A Do­main Spe­cific Lan­guage for Re­pro­du­cing Con­cur­rency Bugs (pdf)
    Tayfun El­mas, Jacob Burnim, George Nec­ula, Koushik Sen.
    In Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI). 2013.

  • Con­cur­rency Testing Using Schedule Bound­ing: an Em­pir­ical Study (pdf)
    Paul Thom­son, Alastair F. Don­ald­son, and Adam Betts.
    In Sym­posium on Prin­ciples and Prac­tice of Par­allel Pro­gram­ming (P­PoPP). 2014.

  • Dy­namic Par­tial Order Re­duc­tion for Re­laxed Memory Models (pdf)
    Naling Zhang, Markus Kusano, and Chao Wang.
    In Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI 2015). 2015.

  • Asyn­chronous Pro­gram­ming, Ana­lysis and Testing with State Ma­chines (pdf)
    Pantazis De­li­gi­an­nis, Alastair F. Don­ald­son, Jeroen Ketema, Akash Lal, and Paul Thom­son.
    In Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI). 2015.

  • State­less Model Checking Con­cur­rent Pro­grams with Max­imal Caus­ality Re­duc­tion (pdf)
    Jeff Huang.
    In Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI). 2015.

  • Con­cur­rency Testing Using Con­trolled Sched­ulers: An Em­pir­ical Study (pdf)
    Paul Thom­son, Alastair F. Don­ald­son, and Adam Betts.
    In Trans­ac­tions on Par­allel Com­puting (TOPC). 2016.

  • Un­cov­ering Bugs in Dis­trib­uted Storage Sys­tems during Testing (not in Pro­duc­tion!) (pdf)
    Pantazis De­li­gi­an­nis, Matt Mc­Cutchen, Paul Thom­son, Shuo Chen, Alastair F. Don­ald­son, John Er­ick­son, Cheng Huang, Akash Lal, Rashmi Mud­du­luru, Shaz Qadeer, and Wolfram Schulte.
    In Con­fer­ence on File and Storage Tech­no­lo­gies (FAST). 2016.

  • Pro­moting Sec­ondary Or­ders of Event Pairs in Ran­dom­ized Scheduling using a Ran­dom­ized Stride (pdf)
    Mah­moud Ab­delra­soul.
    In Con­fer­ence on Auto­mated Soft­ware En­gin­eering (ASE). 2017.

My pa­pers

  • Déjà Fu: A Con­cur­rency Testing Lib­rary for Haskell (pdf)
    Mi­chael Walker and Colin Runci­man.
    In Sym­posium on Haskell (Haskell). 2015.

Venues

  • Con­fer­ence on Auto­mated Soft­ware En­gin­eering (ASE)
  • Con­fer­ence on File and Storage Tech­no­lo­gies (FAST)
  • Con­fer­ence on Pro­gram­ming Lan­guage Design and Im­ple­ment­a­tion (PLDI)
  • In­ter­na­tional Con­fer­ence on Ar­chi­tec­tural Sup­port for Pro­gram­ming Lan­guages and Op­er­ating Sys­tems (AS­PLOS)
  • In­ter­na­tional Con­fer­ence on Auto­mated Soft­ware En­gin­eering (ASA)
  • In­ter­na­tional Con­fer­ence on Ob­ject Ori­ented Pro­gram­ming Sys­tems, Lan­guages & Ap­plic­a­tions (OOPSLA, now SPLASH)
  • Sym­posium on Prin­ciples and Prac­tice of Par­allel Pro­gram­ming (P­PoPP)
  • Sym­posium on Prin­ciples of Pro­gram­ming Lan­guages (POPL)
  • Trans­ac­tions on Par­allel Com­puting (TOPC)

Test case gen­er­a­tion

Test cases are hard to write by hand, so rather than do that, have a tool at­tempt to dis­cover in­ter­esting ones. By reading the out­put, a pro­grammer can (a) add good tests to the test­suite; and (b) spot po­ten­tial is­sues when ex­pected tests don’t show up, or when un­ex­pected ones do.

Pa­pers

  • In­creasing Func­tional Cov­erage by In­ductive Test­ing: A Case Study (pdf)
    Neil Walkin­shaw, Kirill Bog­danov, John Der­rick, and Javier Paris.
    In Con­fer­ence on Testing Soft­ware and Sys­tems (ICTSS). 2010.

  • Quick­Spec: Guessing Formal Spe­cific­a­tions Using Testing (pdf)
    Koen Claessen, Nich­olas Small­bone, John Hughes.
    In Con­fer­ence on Tests and Proofs (TAP). 2010.

  • Swarm Testing (pdf)
    Alex Groce, Chaoqiang Zhang, Eric Eide, Yang Chen, and John Regehr.
    In In­ter­na­tional Sym­posium on Soft­ware Testing and Ana­lysis (IS­STA). 2012.

  • Fit­Spec: re­fining prop­erty sets for func­tional testing (pdf)
    Rudy Braque­hais and Colin Runci­man.
    In Sym­posium on Haskell (Haskell). 2016.

  • Gen­er­ating Fo­cused Random Tests Using Dir­ected Swarm Testing (pdf)
    Mo­hammad Amin Ali­pour, Alex Groce, Rahul Gop­inath, and Arpit Christi.
    In In­ter­na­tional Sym­posium on Soft­ware Testing and Ana­lysis (IS­STA). 2016.

  • Quick Spe­cific­a­tions for the Busy Pro­grammer (pdf)
    Nich­olas Small­bone, Moa Jo­hans­son, Koen Claessen, Max­imilian Al­ge­hed.
    In Journal of Func­tional Pro­gram­ming (JFP). 2017.

  • Dis­cov­ering Re­la­tional Spe­cific­a­tions (pdf)
    Calvin Smith, Gab­riel Ferns, and Aws Al­bar­g­houthi.
    In Found­a­tions of Soft­ware En­gin­eering (F­SE). 2017

  • Spec­u­late: Dis­cov­ering Con­di­tional Equa­tions and In­equal­ities about Black­-Box Func­tions by Reas­oning from Test Res­ults (pdf)
    Rudy Braque­hais and Colin Runci­man.
    In Sym­posium on Haskell (Haskell). 2017.

Venues

  • Haskell Sym­posium (Haskell)
  • In­ter­na­tional Con­fer­ence on Testing Soft­ware and Sys­tems (ICTSS)
  • In­ter­na­tional Con­fer­ence on Tests and Proofs (TAP)
  • In­ter­na­tional Sym­posium on Soft­ware Testing and Ana­lysis (IS­STA)
  • Joint European Soft­ware En­gin­eering Con­fer­ence and Sym­posium on the Found­a­tions of Soft­ware En­gin­eering (ESEC/FSE)
  • Journal of Func­tional Pro­gram­ming (JFP)

Test case re­duc­tion

Once we have pro­duced (either hand-written by a pro­grammer or gen­er­ated with a tool) a test case which ex­hibits some fault, we want to throw away all the in­cid­ental com­plex­ity, and find the simplest test case which ex­hibits the same bug.

This over­laps heavily with test case gen­er­a­tion, but dif­fers in mo­tiv­a­tion.

People

Pa­pers

  • Prac­tical Se­mantic Test Sim­pli­fic­a­tion (pdf)
    Sai Zhang.
    In In­ter­na­tional Con­fer­ence on Soft­ware En­gin­eering (IC­SE). 2013.

  • One Test to Rule Them All (pdf)
    Alex Groce, Josie Holmes, and Kevin Kel­lar.
    In In­ter­na­tional Sym­posium on Soft­ware Tetsing and Ana­lysis (IS­STA). 2017.

Venues

  • In­ter­na­tional Con­fer­ence on Soft­ware En­gin­eering (ICSE)
  • In­ter­na­tional Sym­posium on Soft­ware Testing and Ana­lysis (IS­STA)

  1. Bold people are those who, at the time of writ­ing, I con­sidered to be key fig­ures in the field to keep an eye on.