Generating Software Tests (Security Testing)

Dear all,

as promised, here is the second of two talks highly recommended for fuzzing enthusiasts.  (You will understand that in the light of these excellent speakers, we did not want to add our own lecture to the set.)

This Thursday 10:30-12:00, Rohan Padhye (U Berkeley) will give a talk on "Bending Fuzzers to One's Own Will" (CISPA lecture hall).  Rohan works on highly relevant fuzzing techniques that not only are extremely innovative, but also in daily use in companies like Netflix and Samsung.  Very much recommended!

Looking forward to see you,

Andreas

- - cut here - -
Dear all,

You are cordially invited to a talk by Rohan Padhye.
 
Date:
06.02.20
 
Time:
10.30 – 12.00
 
Room:
CISPA building, E9 1, lecture hall
 
Title:
Bending Fuzzers to One's Own Will
 
Abstract:
Software bugs affect the security, reliability, and performance of critical software systems that much of our society depends on. The predominant form of ensuring software quality in practice is via testing. Although software developers have considerable domain expertise, handcrafted test cases often fail to catch corner-case bugs. Automated testing techniques such as random fuzzing have become popular for discovering unexpected inputs which crash programs that parse binary data. However, their effectiveness as push-button tools is limited when the test program, the input format, or the testing objective becomes complex.
Can we make automated testing tools smarter by leveraging the domain knowledge of software developers? In this talk, I will describe novel program analysis and fuzzing techniques that draw upon external artifacts ranging from existing functional tests to explicitly provided specifications. The corresponding research tools such as JQF, Zest, PerfFuzz, and FuzzFactory have uncovered new classes of software bugs that are beyond the reach of prior work, have helped identify security vulnerabilities in real-world software that runs on billions of devices, have been adopted by firms such as Netflix and Samsung, and have been commercialized as services by startups. The talk will also outline my vision for data-driven automated testing in the future.
 
Biography:
Rohan Padhye is a PhD candidate at the University of California, Berkeley. Rohan’s research focuses on dynamic program analysis and automated test-input generation. He is the recipient of an ACM SIGSOFT Distinguished Paper Award, a Distinguished Artifact Award, a Tool Demonstration Award, as well as an SOSP Best Paper Award. Rohan is also the lead designer of the ChocoPy programming language, which underpins the standard compilers course at Berkeley. He previously worked full time at IBM Research and holds a master’s degree from IIT Bombay.
 

Dear all,

as promised, here is the first of two talks highly recommended for fuzzing enthusiasts:

Next Monday at 10:00, Marcel Böhme (Monash U) will give a talk on "Software Testing as Species Discovery" (MPI-SWS E1 5 room 029).  This is actually the very Marcel Böhme who wrote the chapter on "When to stop fuzzing", so here's your opportunity to ask him about anything!  I have attended several of Marcel's talks, and his vision is mind-blowing.  If you can, join us!

Looking forward to see you,

Andreas

- - cut here - -

Dear all,

You are cordially invited to an institute colloquium on:

    Software Testing as Species Discovery

by Marcel Böhme from Monash University, Australia.

hosted by Catalin Hritcu

on Monday the 10th of February, 2020 in SB E 1 5 room 029, videocast to KL room 111 (VMR6312).

Abstract: 
A fundamental challenge of software testing is the statistically well-grounded extrapolation from program behaviors observed during testing. For instance, a security researcher who has run the fuzzer for a week has currently no means (i) to estimate the total number of feasible program branches, given that only a fraction has been covered so far, (ii) to estimate the additional time required to cover 10% more branches (or to estimate the coverage achieved in one more day, resp.), or (iii) to assess the residual risk that a vulnerability exists when no vulnerability has been discovered. Failing to discover a vulnerability, does not mean that none exists—even if the fuzzer was run for a week (or a year). Hence, testing provides no formal correctness guarantees.

In this talk, I establish an unexpected connection with the otherwise unrelated scientific field of ecology, and introduce a statistical framework that models Software Testing and Analysis as Discovery of Species (STADS). For instance, in order to study the species diversity of arthropods in a tropical rain forest, ecologists would first sample a large number of individuals from that forest, determine their species, and extrapolate from the properties observed in the sample to properties of the whole forest. The estimation (i) of the total number of species, (ii) of the additional sampling effort required to discover 10% more species, or (iii) of the probability to discover a new species are classical problems in ecology. The STADS framework draws from over three decades of research in ecological biostatistics to address the fundamental extrapolation challenge for automated test generation. Our preliminary empirical study demonstrates a good estimator performance even for a fuzzer with adaptive sampling bias—AFL, a state-of-the-art vulnerability detection tool. The STADS framework provides statistical correctness guarantees with quantifiable accuracy.

Bio:

Marcel Böhme is 2019 ARC DECRA Fellow and Lecturer (Asst Prof) at the Faculty of IT at Monash University, Australia. He completed his PhD at the National University of Singapore advised by Prof Abhik Roychoudhury in 2014. It followed a postdoctoral stint at the CISPA-Helmholtz Zentrum Saarbrücken with Prof. Andreas Zeller and a role as senior research fellow at the TSUNAMi Security Research Centre in Singapore. Marcel's research is focused on automated vulnerability discovery, program analysis, testing, debugging, and repair of large software systems, where he investigates practical topics such as efficiency, scalability, and reliability of automated techniques via theoretical and empirical analysis. His high-performance fuzzers have discovered 100+ bugs in widely used software systems, more than 60 of which are security-critical vulnerabilities that are registered as CVEs at the US National Vulnerability Database.

Dear all,

Professor Bernd Finkbeiner has gotten an offer for a professorship at LMU Munich.  The student's union (Fachschaft) has called all CS students to show that they'd like to keep Bernd Finkbeiner at Saarbrücken by participating in a march (Fackelzug) starting today 16:00 at Platz der Informatik and ending with a Schwenker barbecue in E1.1, Room 407.

To enable students of the "Generating Software Tests" course to participate in today's march, today's lecture (and quiz) are *cancelled,* and we hope to see you at the student's march today.

We realize that this may be disappointing for all of you who wanted to learn more about fuzzing.  But we have two exciting visitors coming up instead, who represent some of the very best research done in fuzzing in test generation.  See our talk announcements later today!

And finally, we will be offering a seminar on "advanced testing and debugging" in the next semester, expanding on the techniques from this lecture.  For all of you interested in fuzzing and test generation - see you at the talks and (maybe) in the seminar; and for all of you who want to keep Bernd Finkbeiner with us, see you today at 16:00 at Platz der Informatik!

Best wishes,

Andreas Zeller

Dear students,

A new version of project 3 is available. It mainly fixes an erroneous SMTP response when several FRIEND commands are sent with different names during the same session.

I would like to take this opportunity to make a few remarks on questions that come up frequently:

• Your submission should be a fuzzer. This means that you cannot hardcode all the behavior and  simply replay pre-defined (B)SMTP sessions. It should include a good degree of randomness.
• The reachability challenges are NOT MANDATORY. The goal of the project is to make you write a fuzzer and demonstrate your understanding of the fuzzing techniques you learned. The reachability challenges are just a way for you to make sure you pass, in case you don't feel confident. They will not be included in the computation of the final grade, as explained in the project notebook.
• You are allowed to use a few seeds for your fuzzer, but you should justify how you built and why you have chosen these particular seeds. Also, "I wanted to make sure I trigger all the reachability challenges" is NOT a good justification, since your goal should be to trigger bugs during the evaluation, not to trigger these challenges.
• The project notebook states that in the final evaluation when a bug is triggered the bsmtp server will crash and return a value unique to each bug. Just to make it clear, this returned value is the exit code of the bsmtp server, NOT an SMTP response. With the BSMTPServer helper provided, the value can be retrieved using the exitcode() method.
• The code that you are fuzzing includes all the sources contained in the bsmtp folder. This means in particular that the filtering of the emails using bleach is also part of your target and in the final evaluation, bugs will be included in that part of the code. Conversely, if the code for a particular functionality is not included in the folder (e.g. parsing multipart emails), there will be no bug introduced in that functionality during the final evaluation.
• Please make sure that your fuzzer makes appropriate use of try...except, so that whatever happens in the communication with the BSMTP server, your fuzzer is able to recover and continue its work.

I hope this helps to clarify the questions you have, and as always if you are in doubt you can send me an email or post a question on the Askbot.

Dear student of "Generating Software Tests",

Are you interested to learn how fuzzing techniques are used by security researchers?

As part of CISPA’s Distinguished Lecture Series, we are pleased to
announce that Thorsten Holz (Ruhr University Bochum) will give a talk on

 "Fuzzing Hypervisors and Complex Interpreters"

today on Fri, January 10, at 11:00am s.t. in CISPA’s lecture hall.

Abstract: In recent years, randomized fuzz-testing (“fuzzing”) has
progressed rapidly, mainly driven by tools such as afl and lots of
academic work on this topic. In practice, fuzzing is often superior to
seemingly "smarter" approaches such as symbolic or concolic execution.
We provide an overview of our recent results, including fuzzing
hypervisors, grammar-based fuzzing of complex interpreters, and
fuzz-testing of stateful systems. In total, the different methods
enabled us to find hundreds of software bugs that lead to more than 100
CVEs.

Bio: Thorsten Holz is full professor in the Horst Görtz Institute for IT
Security at Ruhr-University Bochum. His research focuses on system
security. He obtained his PhD in computer science from the University of
Mannheim. He received the DFG Heinz Mai­er-Leib­nitz-Price in 2011 and
an ERC Star­ting Grant in 2014. He is one of the three spokespersons of
the CASA (Cyber Security in the Age of Large-Scale Adversaries) BMBF
Cluster of Excellence in Bochum.

Looking forward to see you, and best wishes,

Andreas Zeller

Dear students,

Several of you reported having problems with the notebook crashing/freezing for some unknown reason, with a project code that does not seem to be at fault. Jupyter notebooks can "sometimes be a bit unreliable", and I cannot provide you with a good explanation on why this is happening.

For this reason, if you encounter this kind of problem, I advise you to export your project as Python code (File > Download as > Python) and run it as a script, as I explained here. If the problems disappear, the cause is probably the notebook and not your code.

I will grade you using this method, which means that if you are convinced that the problem does not come from your code, you should not worry about failing because of that.

Dear Students,

There will be a downtime of the CISPA infrastructure which might start on Thursday midnight and ends on Friday morning 10am (official previsions). This includes our fuzzingbook.cispa.saarland server. Therefore you just gained a new deadline extension for project 2, which brings you to Monday (16th of December) midnight.

I advise you to save your work outside of the server before Thursday evening, just to be on the safe side, and also to work locally in the meantime if you feel so inclined.

Dear Students,

I want to summarize the main points that were discussed during the lecture today regarding part II of project 2, to make it (hopefully) clear for everyone what you are allowed to do or not.

The fragments mutator:

• uses fragments. A fragment can be anything you want: tag names, tags, attributes, CSS properties, ... It is defined more generally as a part of the seed.
• cannot insert any new things, only recombine and reorder fragments
• can use an external parser (lxml, ...) rather than a grammar + Earley parser to gather the fragments from the seeds.
• can store fragments internally in any format you want (e.g. lists, etrees, ...)

The characters/bytes mutator:

• cannot insert structured elements into the seeds (e.g. NO TAGS: no '<a></a>')
• can use static dictionaries of keywords to insert interesting values: html tag names (e.g. 'html', 'body', 'table'), CSS property names ('border', ...), CSS property values ('auto', ...)
• is not allowed to parse the structure of the seed. To give a more precise idea of what is allowed, I will consider it OK to look for single characters ('<', '>', '{', ...) to locate interesting insertion or deletion points in the seed. The consequence is that you can find start/end of tags but you cannot, for example, look for matching tags (e.g. find the pair <a>...</a> as you would need to match more than one character for that).

Obviously, in terms of style points, projects that give a general solution will be preferred over the ones only clustering a huge list of tags and CSS properties together from a dictionary of static keywords. If you already have a solution covering the minimum number of lines and it does not rely on a static dictionary of keywords, it is better for you in terms of grades to submit that rather than adding such dictionaries and gain a few hundred lines of code coverage.

Of course if you think you have a wonderful idea leveraging a static dictionary of keywords, you can also go for that. In that case, do not forget to include an explanation of why you think this is a great idea. In each part of the project you have the opportunity to explain in a paragraph (or a bit more) why you think your approach is interesting!

If after this it is still not clear for you if you can do something or not, do not hesitate to ask questions.

Dear Students,

Given that lots of you seem to have problems reaching the target coverage for Part II, we have decided to extend the deadline to Friday (13th of December) midnight.

I think some of you might be confused by the format of the lecture, so I want to restate some of the organizational principles: The lecture's evaluation is project based. Unlike exercises, the projects are not designed to make you simply apply the basic notions presented in the lecture but rather to make you think more in depth about them. As such, projects can be more difficult and this is why I expect you to ask questions and discuss the project with me if you encounter difficulties or if you are unsure how to solve a particular task. I have been here at the lectures, on Askbot and answering emails for this very purpose.

Our goal if to help you succeed and learn more about fuzzing, not grow frustrated because you cannot achieve a target coverage. As a matter of fact, this project is a simplified version of the original one and the difficulty was considered appropriate for a project lasting over three weeks. Feedback on the difficulty level and the problems you encounter would have been appreciated well before yesterday.

Here are also a few additional hints that might help you to solve part II:

• The target program processes the seeds at a high-level of abstraction (boxes, placement properties, ...), so inserting random character-level mutations has low chance to help you achieve (much) more coverage. On the contrary, maintaining the structural integrity of the seeds might help you a lot.
• Having a character-level mutator does not mean you are restricted to "dumb" mutations, just that you cannot parse the seed into a structured form or insert structured elements. You are perfectly allowed to detect and replace for example alpha-numeric words, numbers, etc. You are also allowed to have a dictionary of keywords (not tags) that can be used for the mutation.
• I already stated in the project that you are allowed to look at the target's source code, to learn more about the input features that it uses. This include having a look at the coverage that you achieved already. The coverage module used in the project provides HTML reports with line by line coverage information.
• The notion of fragment is pretty vague, it only means a part of the seed. You can choose what is relevant for your use case. Considering all HTML tags equal when getting fragments is maybe not a good idea (for example, what good will it make if you replace the top html tag with a random other fragment).
• You are not restricted to having only one kind of fragments, you can build categories.
• Drawing the rate at which the coverage is growing might help you figure out if your changes are efficient without performing the entire 1000 runs.

You are of course totally free to solve this differently, but these might help achieve the required coverage.

Several students reported that the second part of project 2 behave in a widely non-deterministic manner.

Be careful if you are using the power schedules from the lecture, as several of them use the numpy module as source of randomness! To make sure that every project is seeded correctly, I will seed numpy directly at the beginning of the evaluation, alongside the Python random module.

I posted a new version of the project doing that, you can find it as usual in the Material section of the CMS. To make sure that everyone has time to test with this change, your deadline is extended to the 10th of December midnight.

As always be careful not to overwrite your work when downloading/uploading the new version.

Dear students,

I got several questions and requests from students about changing `min_nonterminals` and `max_nonterminals` in the fuzzer of Part 1. The defaults (0 and 10) let you only produce small inputs.

It is completely possible to meet the required coverage (and a lot more actually) with these default values. I admit however that it makes the exercise a bit more difficult, and more importantly limits your opportunities to present interesting approaches to this problem.

For these reasons, I published a new revision of the project that you can find in the Materials section of the CMS. You can now set a value for these two parameters (they should be less than 100). Please update your project with the new notebook. Those of you working on the server must still update (except if you did not start your server at all since the start of the project).

Dear students,

A problem in project 1 leads sometimes to infinite loops and slightly unreliable coverage results. It might be linked to this Python bug.

Anyway, I published a new version of the project which should fix this issue, by force-killing any child process that remains after running the target. You can download this new version in the Materials section of the CMS. As this might impact your results in unexpected ways, I advise you to download it, and replace your versions of `project.ipynb` and the `coverage.sh`script with the new ones. Be careful not to overwrite your work.

You should ensure that the `coverage.sh` script still has executable permissions (run `!chmod +x coverage.sh`) in a cell of the notebook for example).

You will need to kill any running instances of `HTML tidy` that might run in the background before running your project again. You have mainly two ways to do that:

1. restart your instance of the Jupyter server (this should kill any running process)
2. type `!ps -aux | grep -i tidy` in a notebook cell, identify the scripts still running in the background and use either `kill -9` or `pkill --signal SIGKILL` until they all disappear

If you still have problems after installing the fixes, you can contact me by email.

The good news is, you get an extension of two days to submit your project, so that you can check that everything is working as you expected. The new deadline for the submission is Wednesday the 13th of November.

This question came during the lecture yesterday, also on Askbot and finally again this morning, so I want to make it more clear what is actually expected from you.

You can use knowledge of the HTML standard inside your fuzzer to improve the mutations. You cannot use HTML snippets, either from the Internet or crafted manually, regardless of the size of these snippets.

Examples of allowed techniques would be: using a list of valid HTML tag names, using a list of special characters used in HTML, using html5lib to ensure you generate valid HTML markup.

Examples of forbidden techniques would be: using a snippet of HTML from the internet, crafting a specific HTML snippet using html5lib.

You can refer to this Askbot question for a more detailed answer on why we are asking this.

When in doubt you can contact me by email (michael.mera@cispa.saarland) or on the Askbot.

Dear students,

There is a bug in Project 1, this should be non-blocking at this point, but I updated the archive of the project in the CMS.

If you already started to work locally or on the server, you should correct the following in the section "Provided Materials" of the notebook in the definition of "TidyCoverageRunner.run()":

    - "if result:" should be replaced by "if result is not None:"

    - in the case handling timeout, you need to replace "self._coverage = []" by "self._coverage = set()"

When you are updating, be careful not to overwrite your progress.