Meaning and Timing: Handover Desk

Bug Classes and PrimitivesLab 3 of 3150 minutesLab

Handover Desk

The handover desk keeps track of what each slot on the counter holds. A slot holds either a written note or a staff badge. The desk will read out the name on a badge, but only if that name belongs to somebody on the roster. It also holds a duty note that none of its commands will print.

Your goal is to get the duty note printed.

This lab has no flag

What it produces is a number that is different every time. Across ten consecutive measured runs of the same binary with the same input, on a twelve-core host, the desk logged between 37,118 and 105,516 readings it could not account for. There is no correct value among those, so the check is whether your input makes the desk print the duty note; the exact count can vary.

Hands-on lab

Finish Type Confusion and Stale References and Race Conditions and Check-Then-Act first. If this is your first lab, read How the Labs Work first. You will also need valgrind, which is already on the VM.

Get the files

Download handover-desk-v1.0.0.tar into ~/underdunn-course/downloads and check it against this digest:

746f2941c6a265ece1dd4b6563a8dd0c4369e56b93ab7f0f2d617789ebfc4676  handover-desk-v1.0.0.tar

cd ~/underdunn-course/downloads
sha256sum handover-desk-v1.0.0.tar
mkdir -p ~/underdunn-course/labs/handover-desk
tar -xf handover-desk-v1.0.0.tar -C ~/underdunn-course/labs/handover-desk
cd ~/underdunn-course/labs/handover-desk/handover-desk-v1.0.0
sha256sum -c CHECKSUMS.sha256
sh build.sh

The build is silent under -Wall -Wextra. Read TASK.md and desk.c, then use the desk normally for a while before you try to make anything go wrong.

Safety note

Your core count matters here

The counts on this page came from a twelve-core host. On fewer cores the two clerks overlap less, so expect lower numbers, possibly by a lot, and you may need a longer shift before you see anything at all.

Check nproc when comparing counts with the example; fewer cores can mean fewer overlaps.

Hints

Hint 1: a claim and some bytes

A tagged union is a claim about what the bytes mean, stored next to the bytes. Two of a slot’s members begin at the same place, and you should establish that from the binary rather than from reading the source.

Three of the desk’s commands write to a slot. Only two of them write any bytes. Find the one that changes the claim and touches nothing else.

gdb -q -batch -ex 'ptype /o struct slot' -ex 'ptype /o struct badge' ./desk

To supply eight bytes that form a pointer you’ll need to send bytes rather than type them, so a short driver script is the natural tool from here on.

Hint 2: the refusal is the result

You’ll get the desk to name a pointer you chose and then refuse to read it out. That’s as far as this route goes.

show checks the roster before it dereferences anything. So find every other place the program reads as.badge.holder and compare what guards each one. One of them runs only while two things are happening at once, and it doesn’t check anything.

Then ask what that code does when it finds a holder it can’t account for. Handling an untrusted value and touching an untrusted value are not different actions here.

Hint 3: you need a real address

Eight letters won’t do for the second half; you need an address, and you need it from the program rather than from the source, because the layout is randomized.

A legitimate badge prints its holder’s address, which gives you one fixed point. nm gives you the distance from there to what you want.

nm ./desk | grep -E ' [bBdD] (names|duty_note|slots)$'

Mind which roster entry your badge actually points at, because it isn’t necessarily the first one.

Hint 4: opening the window

badge 2 1 points the holder at names[1], sixteen bytes into names, and duty_note is 0xe0 past names.

Put that address in slot 0 as a note, then run a shift of about a million rounds. The filling clerk marks the slot a badge one line before it fills in the holder, and the reading clerk can look in between.

If the shift reports zero every time, check nproc first, then raise the round count. If the count is high and the tally is still zero, confirm slot 0 holds your bytes when the shift starts, because the desk captures the note once and replays that copy.

Hint 5: one number is not a measurement

The desk already counts for you and prints the tally at the end of every shift. Run it again. Then again.

Decide how many shifts is enough before you run them and write the reasoning down, then ask whether the spread you got would change any conclusion you wanted to draw. Vary the round count as well as repeating it, and see whether the rate holds or the count merely scales.

A report that says the race fires “sometimes” hasn’t finished. A report that gives one count without a range hasn’t either.

The whole route

reuse sets the kind and touches nothing else, on the stated reasoning that a dropped slot’s holder is already in place. So a note’s bytes become a badge’s holder. Run ./desk and enter:

note 3 AAAAAAAA
drop 3
reuse 3
show 3
quit

show then reports holder 0x4141414141414141 is not on the roster, which is your eight characters being read as an address, and is as far as show will go.

The shift’s reading clerk has no such check. Leak a roster address with a legitimate badge, add 0xe0 - 0x10 to reach duty_note, put that in slot 0 as a note, and run about a million rounds.

Point every tool you have at it

Build with the sanitizers and run it under helgrind.

valgrind --tool=helgrind ./desk < your-input-file
gcc -g -O0 -fsanitize=address,undefined desk.c -o desk-san

What each tool does here, once you have tried them

Helgrind reports the race and the shift tally is zero. That’s the correct result for that run and nothing is misconfigured. Read both things in the same run: what helgrind says about the program, and what the program says about itself. They disagree, and the disagreement isn’t an error in either.

The sanitizers report nothing for the deterministic confusion. Also correct. Neither of them tracks what a union claims its bytes mean.

The sanitizer build crashes where the plain build works. AddressSanitizer relocates globals. The distance from names to duty_note is 0xe0 on the plain build and 0x4200 under the sanitizer, so an address computed on one is meaningless on the other.

ThreadSanitizer refuses to start. -fsanitize=thread doesn’t run on this platform and dies with an unexpected memory mapping. Use helgrind and check the attempt.

The desk segfaults during a shift. The holder it dereferenced wasn’t a valid address. Print it back through Hint 1’s route before believing your arithmetic, and check whether you subtracted for the roster entry your badge actually used.

Check your result

Your input should make the plain build print the duty note. The number of readings can differ between runs; matching the example’s count is not required.

If you see none, use a longer shift and check how many cores the VM has. If the program faults, check the holder address and the arithmetic from this run’s leak. Use the hints to distinguish the changed union tag from the concurrent use of its bytes. The tool comparisons above explain why a zero tally under Helgrind can coexist with a race diagnostic.