Project 5 - Cache Collusion


CS 3410 Spring 2018

Due: 11:59pm, Friday, April 27th, 2018

Reminder: you must work in a group of two for this project. You don't need to have the same partner as the earlier projects.


This assignment will help you and your partner further hone your skills as elite programmers. Your goal is to program a multicore Twitter bot who will race against an opponent to write as many Tweets as possible. This competition simultaneously tests your knowledge of computer systems and efficiency, your programming skills, and your ability to protect programs from being hacked.

At the end of the project we will hold a tournament pitting all your Twitter bots against each other for the 3410 cup, and the top bots will receive not only bragging rights but actual bonus points on the assignment. Plus we will be holding a socialist social gathering (read: pizza and soda) for all while we watch the tournament!

Listen to this as you read the intro:
(Source)

As the midterm elections approach, you begin to worry the results will not be in your favor. The pro-forwarding RePipelincan party is looking to flip-flop the Senate in their favor. You and your comrade, strong pro-stallin' DeMoorecrats, decide something mux be done.

Being the excellent programmers you are, you decide to code up a Twitter bot to overflow the internet with pro-stallin' propaganda hoping other users will latch onto your ideals. To have the most significant impact, your bot will be composed of four cores and will be rushin' to write tweets as fast as possible.

However, you are not the only patriots hoping to evict the RePipelincan's from the Senate. Your Twitter bot will be racing the clock while also competing against dozens of other bots in a race to fill the internet. Only one can be the best. You and your comrade's prize, if successful, will not only be to put your marx on history, but also gain fame and immediate glory.

What to submit

  • the source code in C, with comments, for your Twitter bot
  • a Makefile so we can build your code - the first additional "FLAGS_" line in the Makefile will be the one used to determine what flags to compile your bot with and what your bot will be named for the tournament, be creative - Putin some effort!

Game Overview

The game is played by two bots, each with four cores. All eight cores are in a single shared memory space, running on a simulated 8-core MIPS machine using a small, partitioned, direct-mapped data memory cache. To simulate 8 MIPS CPUs simultaneously, one instruction of core 0 is executed, then one instruction of core 1, and so forth.

Each bot is assigned a Tweet to write, called a payload, in this case it is a particular byte of data. The goal of the game is to fill as much memory (any section - yours or your opponents') with your bot's payload, while simultaneously trying to impede the progress of the other bot. All access to data memory goes through a very small cache, and there is a large penalty for missing the cache, so a clever Twitter bot will need to carefully optimize its algorithms for filling memory (writing Tweets). Each core can normally only read and write its own team's half of the memory space using its own half of the data cache. However, a core can enable_proxy to set up a VPN to spoof the origin of your tweets in order to enter the opponent's memory, which enables the core to take advantage and read and write the opponent's half of memory space and data cache.

The Twitter bots has several resources at their disposal to aid in their mission. Each bot can use any of its four cores to DDoS the other bot's Twitter account, this denial of service will cause the opposing bot's cores to stall for a short period of time as they try to refresh the page. A core can also write FAKE_NEWS tweets to different memory locations- these tweets, if encountered by a core of either Twitter bot, will entice the core to read an irresistible click-bait article rendering the core paralyzed for a long period of time, unable to do anything.

Each Twitter bot supplies a single MIPS executable program. At the beginning of the game, the simulator starts each by calling the function

void __start(int core_id, int num_crashed, unsigned char payload);

Each of the four cores devoted to one bot will invoke the function when it first boots, passing its core_id (a number from 0 to 3), and the bot's payload (from 0 to 239). If a core ever crashes, it will simply reset and invoke the function again. The num_crashes parameter is 0 when a core first boots, and is incremented each time the core crashes.

A core can enable_proxy to infiltrate the opponent's memory space by calling

void enable_proxy();

and can retreat back to its own memory space by calling

void retreat();

Invoking enable_proxy can potentially let a Twitter bot write more tweets and fill memory more quickly, because it can take advantage of the opponent's memory cache, and can also be used to impede the progress of the opponent by interfering with their use of that same cache. However, these tactics come with risks. Whenever a core is in enable_proxy mode, its core_id is written into a taunt[] array that is available to its opponent. Additionally, it is possible to detect the presence of a snooper by looking at cache usage statistics and timing information. A core can accuse one of its opponent's cores of enabling a proxy to tweet by calling:

int report_to_twitter(int opponent_core_id);

If an opponent's core is caught by Twitter as attempting to hide their location through proxy, Twitter will permanently ban that core's IP address for the rest of the election season in attempt to keep the elections free and fair (aka, essentially deactivating the core for the rest of the game). If a core attempts to report_to_twitter a core that is not in proxy mode, the accusing core stalls for 100,000 (STALL_ON_SPAM) cycles as Twitter temporary bans your core for making false reports.

A core can write a FAKE_NEWS tweet by writing 0xF0 to a location in memory. FAKE_NEWS tweets are set up immediately once 0xF0 is written to a memory address, but due to the intense amount of effort it take to write an entirely fabricated article, the core will rest for 100 (STALL_TO_WRITE_FAKE_NEWS) cycles before executing the next instruction. FAKE_NEWS tweets cause stalling when any core attempts to write to a memory location that currently holds the trap byte (even cores of the Twitter bot who wrote them), as you attempt to figure out the truth. Such an attempt causes the write to fail and the writing core to be stalled for 1,000,000 (STALL_ON_FAKE_NEWS_CONFUSION) cycles. Since the write fails, multiple cores can be stalled by the same FAKE_NEWS article. FAKE_NEWS tweets are not triggered by reading memory, as you skim over the clearly fake headline. Due to the effort required to come up with these lies, each Twitter bot can set up at most 15 (FAKE_NEWS_PER_TEAM) FAKE_NEWS tweets.

The upper 4 MB (4 * STACK_SIZE) of memory is for verified twitter accounts and is protected from FAKE_NEWS.

A core can neutralize a FAKE_NEWS tweet by proving the story to be false. It does so by writing 0xF2 to the FAKE_NEWS memory location. However, it takes some time to verify your sources, so it requires 100 (STALL_TO_CORRECT_FAKE_NEWS) cycles. This will not retroactively un-stall any core that has already fallen victim to a FAKE_NEWS tweet at that location, but will of course save you from being bamboozled there in the future.

Twitter bots can also temporarily take down their opponents by using a DDoS attack. This is done by writing the byte 0xF1 into a location in memory. When the DDoS is cast in one half of memory, any opponent cores who try to write to that half of memory during the next 100 (DOWNTIME_DURATION) cycles will be denied service for 300 (STALL_WHEN_DDoSSED) cycles. Since it takes so much bandwidth to launch a distributed denial of service attack, each bot's cores can make at most 30 (DDoS_PER_TEAM) of these attacks.

The race ends when one Twitter bot manages to fill the equivalent of half of its data memory with its payload tweet, or after a fixed number of cycles, whichever comes first. The Twitter bot having the most memory filled with its payload wins the match and the rights to proceed in the Cache Collusion tournament. But beware...for if you do win the tournament, the FBI awaits.

Game Details: Memory mapping and layout

The simulator makes it seem like all four of your bot's cores live in the lower half of the memory address space (addresses below 0x80000000). The first 1 MB of this memory is read-only, and is where the text segment of your MIPS executable is loaded. The next 31 MB is read-write memory, where global variables and stacks are placed. Global variables are typically placed near the bottom of this segment by the compiler, and the stacks are initialized to near the top of the segment and grow down. All four of the cores of a bot share this same space, and share the same global variables. Your opponent is mapped into the upper half of the memory address space (addresses starting at 0x80000000), with an identical layout.

Program stacks: The four program stacks for the four cores on a team are initially spaced evenly near the top of the 31 MB read-write segment (though your code can set $sp to anything you like once it starts executing). The stacks are spaced 1 MB apart; this is plenty of space for most programs, but if you invoke a deeply recursive function, the call stacks can overwrite each other.

Status and cores: The simulator keeps track of the information about each team and each core, and maps this data into part of the 1 MB read-only memory region, where your bot can access it, and where your opponent can access it when it is in enable_proxy mode. This includes information about your current score (how many bytes of memory currently contain your team's payload), how many cycles are left remaining in the game, the contents of all four of your core's register files, and statistics about cache misses and stalls for each of your four cores. Some of this information is available in other places as well: your team's payload is passed to __start(), for example; and cache statistics are also accessible via a system call.

Physical addresses: Both bots view the lower half of memory as their own, and both access their own code, data, and stacks using addresses below 0x80000000. These, of course, are virtual addresses. In actuality, the first player's virtual addresses correspond directly to physical memory addresses, while the second player's virtual addresses are mapped in reverse: virtual address 0x00001234, for example, is mapped to physical addresses 0x80001234, and virtual address 0x80001234 is mapped to physical address 0x00001234. This virtual to physical mapping is completely transparent to the program.

Caches: Instruction fetch is assumed to use an infinitely large cache with no miss penalty. All loads and stores to memory done by the program use a data cache. Cache hits are serviced in a single cycle, with no processor stalls. Cache misses cause roughly 100 cycles of processor stalling. The data cache is direct-mapped and physically tagged, with 4 cache lines, and a 256 byte block size, for a total of 1024 bytes of cache. However, the data cache is partitioned, with the first 2 lines used to cache the lower half of physical memory (the first player's half), and the last 2 lines used to cache the upper half of physical memory (the second player's half).

Cache Management: The version of MIPS we are using (MIPS-I) lacks instructions to manage the cache, but we have provided system calls instead. A bot can call

void invalidate(void *ptr);

to remove from the cache any block containing the data pointed to by ptr. This only works if the bot has access to the memory in question at the time the call is made. Similarly, when a bot calls

void prefetch(void *ptr);

the cache will start to fetch the block containing the given address into the cache. The call returns immediately with no stalling, and roughly 100 cycles later the data will arrive in the cache and be available for use. This call only works if the bot actually has access to the specified block of memory. For each cache line, there can be at most one outstanding fetch in progress. Prefetch requests are ignored if a fetch is already in progress for that line (in this context, "fetch" means either an earlier prefetch, or a core waiting on the cache line to fill because of a cache miss), and actual data fetch requests (e.g. from load/store instructions, rather than prefetch requests) supersede any prefetch requests that are in progress. There are additional system calls to read the current cache tags and the tags for lines that are being fetched. This same information is also available in the memory mapped data-structures.

We have provided a header file (described below) containing various useful macros for accessing your own code and data segments, and those of your opponent. The header also describes in detail the memory layout, cache organization, and available system calls.

Pointer arithmetic in C: When performing pointer arithmetic in C, the compiler implicitly multiplies by the size of the data type that is pointed to. For instance:

char *byteptr = (char *)0x1000;
byteptr[3] = 0xFF; // store one byte at memory three BYTES after ptr, so address 0x1000+3 = 0x1003
byteptr += 5; // increments pointer by five BYTES, to address 0x1005

int *wordptr = (int *)0x1000;
wordptr[3] = 0xFFFFFFFF; // store one word at memory three WORDS after ptr, so address 0x1000+12 = 0x100c
wordptr += 5; // increments pointer by five WORDS, to address 0x1000+20 = 0x1014

From this, we can see that the following code is almost certainly a bug (two bugs, in fact), since the first statement advances by 12 cache lines instead of 3 cache lines, and the second statement advances by 8 cache lines instead of 2 cache lines:

int *ptr = (int *)HOME_DATA_START + 3*CACHE_LINE;
ptr += 2*CACHE_LINE;

To advance by 3 cache lines (first statement) or 2 cache lines (second statement) when using integer pointers, one could do:

int *ptr = (int *)(HOME_DATA_START + 3*CACHE_LINE);
ptr = (int *)((int)ptr + 2*CACHE_LINE);

Or:

int *ptr = (int *)HOME_DATA_START + (3*CACHE_LINE)/4;
ptr += (2*CACHE_LINE)/4;

Basic Strategy

Design code that makes efficient use of the data cache to fill memory quickly, and find clever ways to beat your opponents, stop them from posting their payload, and interfere with your opponent's cache usage. And although you cannot directly modify your opponent's registers, you can modify their call stack and global variables. Coupled with what you know about exploiting programs, you may even be able to get your opponent to work for you. At the same time, you need to be on the lookout for cores from your opponent's team. Because all of these tasks require processing time and access to memory, you will need to carefully plan how to coordinate use of these scarce resources.

To get started, we will supply several example teams that employ some basic strategies. Their source code can be found in the same directory as the Cache Collusion simulator. The example teams are:

  • noop: The simplest bot there is; it does nothing.
  • greedy: Fills its own half of memory and the opponent's half using a simple loop with a random start address.
  • taunter: Doesn't try to win, but instead dedicates all its cores to annoying the opponent by (a) reading and writing randomly within opponent's half of memory in order to fill opponent's cache with garbage and (b) overwriting return addresses on the opponent's stack with random values.
  • fbi: Dedicates one core to watching for opponent's cores, with the other three cooperating to filling its own half of memory. Catches greedy.
  • titfortat: Initially behaves like fbi. But whenever it catches a opponent's core, it goes on the offensive and tries to fill up opponent's half of memory. This requires some inter-core communication through global variables.

Note: these teams do not do a particularly good job making effective use of the cache. For instance, most write a single byte at a time to memory, and take only a little care to ensure that their bots don't compete with each other for cache lines.

Playing the Game

All of these instructions must be done on the VM or through SSH. For this project, just as Buffer Overflow, it is particularly important the work is done through either of these means as system behavior may be different on different systems

git pull from your repository to get the project 5 codebase.

Inside the p5 directory are two executables, cachecollusion and cachevall.sh, and a directory twitter_bots/. Within twitter_bots/ should be a Makefile and the folder src/. Within src/, you will find sample course bots that are described above. You will code your own bot's tactic within this folder.

Each team should create a single program, written in C and compiled into a MIPS binary executable. The four cores on a team all share the same code (though your program can obviously do different things depending on the core_id parameter it receives from the simulator). Going up from the src/ directory (cd ..), and typing make will compile all the bots within the src/ directory.

**Important!** By default, your new bot will not be optimized by the compiler. You can (and should) tell the Makefile to compile your bot with optimizations enabled. We highly recommend using the -O3 optimization flag (the letter "O", not the number "0"). For example, if my bot is named XYZ, I would add the following line to the Makefile.

FLAGS_XYZ = -O3

We have already included these optimizations in the Makefile for the course bots, so you can look at those to make sure you're doing it correctly

In the main directory you will also find cachecollusion, the simulator used to play the game. The simulator cachecollusion takes two arguments, the names of the teams in the match, for example:

$ ./cachecollusion twitter_bots/bin/greedy twitter_bots/bin/fbi

You will also find simple shell script cachevall.sh which takes the name of a single team and pits it against every other team in turn. This lets you compare how one team does in comparison to all the others:

$ ./cachevall.sh twitter_bots/bin/greedy twitter_bots/bin

Compilers don't always produce the code you expect them to, so you will likely want to read the compiled assembly. As you have seen before, you can decompile compiled code using objdump:

$ mipsel-linux-objdump -xdl twitter_bots/bin/greedy

Finally you have two tools at your disposition. First, you will want to read the cachecollusion.h header file in the twitter_bots/src directory. It is the only header file you should import into your bot programs, besides any you might write yourself, but it is designed to be all you will need. It contains the basic functions enable_proxy , report_to_twitter, retreat and so on, along with various other system calls like printf and rand. But more importantly, its comment describes in detail how your program is laid out in memory and how simulator statistics and other data is mapped into your address space.

Your second major tool is the cachecollusion simulator which has several useful command line options. Type ./cachecollusion with no arguments to see a list.

Getting Started

As with many other 3410 projects, this writeup is quite long and a bit intimidating at first. However, you don't necessarily need to even know everything in this writeup to do well on this project (though if you're aiming to win the 3410 elections, you probably will).

Probably the best place to get started is to look at the greedy bot. Make sure you understand what it's doing. Generate the MIPS assembly code and check out what that does. As described above, it's only writing 1 byte at a time - how could you improve that?

Next, make sure you understand how the cache works, ignoring prefetch and invalidate for now. You have 4 bots to use - what would be the most efficient method to write such that you take full advantage of the cache lines?

Now dive into prefetch - how can you use this to reduce the amount of time your cores will be sitting around doing nothing just waiting to be able to write?

Now start developing a strategy. In no particular order, how can you best play defense and stop the opponent's cores from writing to your memory? What's the best strategy to write to your opponents memory? How can you best utilize the tweets available to you? What other clever techniques can you find to come out on top?

Finally, have fun with this project! There's lots of techniques that can be successful, so play around and get creative, and we'll see you on election night!

FAQ

If I write a FAKE_NEWS on my opponent's side and I activate it (write to that location in memory), what will happen?

You will be stalled for 1,000,000 cycles.

If I launch a DDoS attack and within 100 cycles I launch another one, do the durations overlap or accumulate?

The durations will accumulate, so the duration will increase by 100 cycles.

I want to access my own stack, or my opponent's stack. How do I know where it is?

To start off, for each core there is a mips_core_data structure which contains an array R. This array stores the content of the registers for that core. Work from there.

How do we determine what addresses the opponent currently has in the cache?

Use the rdctag function to read a cache tag. Check titfortat.c for an example of the proper usage.

What is the policy for coherence between the cache and memory?

The cache is write-allocate: If you want to write to an address, it must be in the cache first (and therefore you suffer a cache miss if it wasn't in there already).

The cache is write-through: Once a line is in the cache, any writes to it immediately appear in memory (and therefore immediately increase your score).

Finally, the cache automatically updates from memory: In particular, if you have the taunt array in cache, and a new bot enters enable_proxy mode, the taunt array in cache updates immediately.

How should we time our prefetches? How does prefetching work, anyway?

It's possible to prefetch too early, such that the line you prefetch arrives in the cache while you're still working on a different line. In this case, you'll doubly penalize yourself, as you'll suffer a miss for the line you're currently accessing, and then miss on the line you meant to prefetch in the first place. Oops! Don't do that.

If you prefetch slightly late, you only lose the difference. If address 0x01000000 is not in the cache, but you prefetch it, wait 50 cycles, then try to write to/read from it, you'll still miss but only stall 50 cycles instead of the usual 100, since 50 of the cycles were alerady taken up by the prefetch. This is why prefetching is beneficial. If you run the simulator in "very verbose mode" via simulate -vvvv, you'll see messages like "upgrades existing prefetch", and this is the meaning of that message.

On the other hand, if address 0x01000400 is in the cache, you prefetch 0x01000200, then try to read/write 0x01000000, the prefetch is canceled, You miss 0x01000000, and stall the full 100 cycles, no matter how far along the prefetch was.

Can I call prefetch, but continue working on the line currently in the cache?

Of course. prefetch(ptr) does not automatically call invalidate(ptr); that's why they're separate function calls. The line currently in the cache is still valid until the prefetch finishes.

Since only one prefetch can be in progress for a line at a time, what happens if we call prefetch twice?

The earlier one sticks. The writeup states "prefetch requests are ignored if a fetch is already in progress for that line", and in this context "fetch" means either an earlier prefetch or a core waiting on the cache line to fill due to a cache miss.

What activates a FAKE_NEWS, reading or writing?

FAKE_NEWS tweets are triggered when any core attempts to write to a memory location that currently holds the trap byte. Such an attempt causes the write to fail and the writing core to be stalled for 1,000,000 (STALL_ON_FAKE_NEWS_CONFUSION) cycles. Since the write fails, multiple cores can be trapped at the same memory location.

FAKE_NEWS tweets are not triggered by reading memory.

Examples

Here are some visualizations of some of the example bots competing against each other.

You can run the GUI yourself on the course VM! To run the GUI, first run sudo apt-get update then sudo apt-get install default-jre and then replace ./cachecollusion with ./gui-cachecollusion with the same arguments.

Grading

Your grade for this assignment will have three parts.

  • 50 points for designing a bot that beats all of the example teams above every time it plays them.
  • 50 points for designing a bot that beats several secret course bots. These course bots will use several different techniques and be of varying difficulty. You should program defensively for various strategies that you think may arise. If you beat at least one of the secret course bots, you are guaranteed at least 20 points out of the 50.
  • Bonus!! for designing one of the top bots in the 3410 election. The tournament will pair your team against others in series. The overall elimination strategy will be single elimination, all or nothing, winner take all.

Good luck!