Specification-Based Testing and Debugging

Dear seminar participants,

Stanimir discovered another problem in the current assignment. In the function "test_tiny_c_interpreter_with_wrong_dict," the "wrong_dict" was initialized only once. However, every call to "interpret_tiny_c" changes the dictionary, resulting in the interpreter being called with a potentially different dictionary every time. A correct implementation of the function looks like this:

def test_tiny_c_interpreter_with_wrong_dict():
    """
    This function tests the Tiny-C interpreter with the metamorphic
    oracle provided by `get_transformation_pair`. It completes normally
    in the case of success and raises an `AssertionError` otherwise.

    This version of `test_tiny_c_interpreter_with_wrong_dict` passes
    a non-trivial initial dictionary to the interpreter to test the
    error-finding capabilities of the metamorphic tester.

    :return: Nothing.
    """

    wrong_dict = tuple({var: 1 for var in string.ascii_lowercase}.items())

    for _ in range(20):
        generator = generate_transformation_pair(
            DEAD_CODE_INSERTION_GRAMMAR_2, TINY_C_GRAMMAR, constraint
        )

        for pair in itertools.islice(generator, 5):
            left = str(pair.filter(lambda node: node.value == "<left>")[0][1])
            right = str(pair.filter(lambda node: node.value == "<right>")[0][1])

            result_left = interpret_tiny_c(left, dict(wrong_dict), gas=20)
            result_right = interpret_tiny_c(right, dict(wrong_dict), gas=20)

            assert result_left == result_right

Mutable data structures are a constant source of trouble in programming. For this reason, I mostly work with immutable types in my research prototypes. Unfortunately, I was not that disciplined when implementing the current assignment.

This could be a nice lesson to be learned. However, you were affected by this problem and might have lost time when trying to work around it. For this, I am very sorry. We will consider this context when grading this part of the assignment.

All the best,
Dominic

Dear seminar participants,

Justin (thanks!) pointed out that the final assertion/check in the "Metamorphic Testing" lab is wrong; it does not call the function `test_tiny_c_interpreter_with_wrong_dict`, but the original `test_tiny_c_interpreter`. Please correct these yourselves.

However, I found a bug at this second call to `test_tiny_c_interpreter`, which is why I missed that problem. The root cause of this bug is the ambiguity of the Tiny-C grammar. For example, the program

{a = 17;if(0) if(1) ; else a = 42;}

has two parses: One equivalent to

{a = 17;if(0) {if(1) ; else a = 42;}}

which is the intended one, and one equivalent to

{a = 17;if(0) {if(1) ;} else a = 42;}

which is the first result returned by the EarleyParser. This latter alternative is not "dead code" and can alter the semantics.

This is an excellent lesson on language ambiguity and the problems one may face when dealing with "grammarware." To solve this, we could resolve the ambiguity in the grammar, replace the grammar-based parser altogether, or adapt the grammar to work with ISLa's "packrat parser." This parser is currently not used since, for the current grammar, packrat runs into an infinite recursion problem.

Long story short:

1. Please change the mentioned function call, and don't be surprised if the original call occasionally also finds an error :)
2. The test routines we're building here, even these simple ones, WORK!
3. Thanks, Justin! For the others: Keep reporting suspicious stuff ;)

Best,
Dominic

Dear seminar participants,

I just updated the solution for the lab on "Oracles." The previous "solution" did not contain solutions; I apologize.

The speakers for our upcoming Delta Debugging/Input Reduction session will be Justin, Moritz, and Sasha. This implicitly defines the three speakers for our final regular seminar session.

Best,
Dominic

bexps_strategy: st.SearchStrategy = st.recursive(
    # The non-recursive base cases.
    st.builds(BTrue) |… Read more

Dear all,

I wanted to share an alternative solution strategy proposed by Stanimir (thanks!) for the arithmetic expressions example in Lab 06.

My proposed solution was

bexps_strategy: st.SearchStrategy = st.recursive(
    # The non-recursive base cases.
    st.builds(BTrue) | st.builds(BFalse) | st.builds(BVar, st.text()),
    # The recursive cases.
    lambda children: (
        st.builds(BNot, children)
        | st.builds(BAnd, children, children)
        | st.builds(BOr, children, children)
    )
)

This approach is inspired by a JSON example using standard Python datatypes such as dicts. In that case, the powerful "builds" strategy cannot work since obtaining information about the intended structure from the ADT definitions is impossible.

I used "recursive" since "build" failed when applied to the abstract "BExp" dataclass. Yet, Stanimir found out that you can join the "builds" for all the cases:

alternative_bexps_strategy: st.SearchStrategy = st.builds(BTrue) | st.builds(BFalse) | st.builds(BVar) | st.builds(BNot) | st.builds(BAnd) | st.builds(BOr)

This more straightforward solution approach should be preferred in practice (for maintainability reasons etc.).

You may also find this helpful. I recommend using Hypothesis where appropriate if you're developing in Python!

Best,
Dominic

Dear all,

Due to conflicting appointments, I have to move our next seminar meeting. We will not meet on Monday, but instead on Wednesday. June 14, 17:00 at the same Zoom link. If you cannot make it on this date, please drop me a note.

Manuel and Mohamad are the designated presenters of the next paper.

Note that the assignment dates stay as they are, so your current assignment will be due on Monday, and the next assignment will also be published on Monday again.

Looking forward to seeing you next Wednesday -- Andreas Zeller

Dear all,

This is to confirm that the assignment sheet for exercise 05 (Testing with Mutations) also contains a solution for Task 1 in the end. This leak was unintended, but cannot be fixed now; at least, it will allow you to compare your solution against the official solution :-) Tasks 2 and 3 still remain to be done, and we wish you lots of enjoyment.

Note that this material will also be the base for the coding assignment in evolutionary fuzzing starting next week, so independent solving is very recommended.

All the best -- Andreas Zeller

Hi everyone,

We found and fixed two bugs in the current compiler testing assignment. Thanks to Stanimir and Faiq for bringing this up!

1. In the AST_ASSIGNMENTS grammar, the definitions of <Assign> and <AugAssign> are wrong. They should read

'<Assign>': [
    'Assign(targets=<nonempty_lhs_expr_list>, value=<expr><type_comment>?)'
]  # was value=<Name>

and

'<AugAssign>': [
    'AugAssign(target=<lhs_expr>, op=<operator>, value=<expr>)'
] # was value=<Name>

respectively.

2. Also in AST_ASSIGNMENTS, the definition of <lhs_expr> is wrong. It should read

'<lhs_expr>': [ '<lhs_Name>', ... ]  # was <Name>

with <lhs_Name> being defined as

'<lhs_Name>': [ 'Name(id=<identifier>, ctx=Store())', ],

These two definitions will enable proper parsing of assignments such as x = 42, and subsequently also with clauses.

We apologize for the confusion. The above changes will make it far easier for you to produce a solution.

Dear all,

I have fixed the "official" start of the seminar to April 24. Note that students are only allowed to register (or withdraw) in HISPOS/LSF for the "exam" within three weeks after the topic assignment or the seminar briefing. Hence, you must register for the seminar in LSF/HISPOS before May 15.

All the best,

Andreas Zeller

 

Update 2023-04-26: Registration in LSF is now open.

Dear seminar participants,

We have set up a preliminary schedule for our seminar. You can inspect the program in the seminar CMS [1], where you can export it to an “.ics” file [2]. We will keep the Zoom link from our kick-off meeting on Monday [3] for the upcoming regular meetings.

Don’t hesitate to contact me with any questions or concerns.

Best,
Dominic

[1] https://cms.cispa.saarland/isla23/termine/calendar/index
[2] https://cms.cispa.saarland/isla23/termine/events/download
[3] https://cispa-de.zoom.us/j/67047831585?pwd=TklENGVVbUw3bGhHRytNMHB3c2dqUT09