CS205Outline.tex

\documentclass[12pt,letterpaper]{article}

\input{common_includes.tex}  %% put includes here. They tend to get reused a lot

\usepackage{lmodern}
\renewcommand*\familydefault{\sfdefault} % use lmodern for paragraphs

\chead{ \fancyplain{}{ CS 205 Course Description } }
\cfoot{ \fancyplain{}{\thepage} }
\setlength{\parskip}{1em}
\setlength{\itemsep}{4em}
\usepackage{indentfirst}

\renewcommand\thesection{} %no section numbers
\renewcommand\thesubsection{\arabic{subsection}} %subsection numbering does not include section

\begin{document}

	\section*{Overview}

	CS205, System Programming and Architecture, was designed for students pursuing the OSU/PSU/UO variant of the CS Major Transfer Map (MTM). Oregon State University and Portland State University both require a lower division course focusing on the interface between high-level code and hardware (CS271 and CS201 respectively. Including the credits for these courses was a critical part of making the MTM workable. This course, while not exactly equivalent to their courses, articulates to those courses. CS205 is optional but strongly encouraged for students bound for UofO where, although it  does not directly articulate to a single course, it does provide coverage of some material that is contained in their lower division sequence.
	 
	The core theme of this course is "What really happens when software runs?" Students should learn how fundamental parts of C programs map to assembly code and binary representations, how this assembly is determined by the Instruction Set Architecture of a machine, the high-level structures of a processor, and the basic facilities provided by an operating system. The particular architecture and assembly studied is not proscribed - students exposed to any modern architecture should be adequately prepared for later courses.

	For colleges that do not teach C as part of their CS161/162/260 sequence, this course also serves the essential role of introducing C programming so students are prepared for Junior year courses that assume a working knowledge of C. Thus, it is assumed that time will be devoted to learning the basics of C programming in addition to learning how C gets mapped to assembly code. After this course, students should be able to write moderately complex, well-structured programs using C. Students should also have experience using a debugger on their code.
	
	Capture The Flag (CTF) style activities that require reading assembly in context and basic dynamic analysis of code using a debugger are a key component of the course. These are intended as a platform to develop hands on skills examining compiled code in static and dynamic contexts and are assumed to be an ongoing thread in the course as opposed to a standalone unit. These activities, or equivalent ones, must be a part of any implementation of CS205 in order to be acceptable for transfer. To aid instructors in meeting this requirement, PSU is providing access to the CTF system they have developed (see CTF section for details). 
	
	The 10th week of this course is designated as time to apply and expand the ideas of the course in a particular context. Three possible approaches - ones that focus on cybersecurity, operating systems, and designing for performance - are briefly outlined in this document to provide suggested uses for this week.
	\clearpage

	
	\section{Course Outcomes}

	Any implementation of CS205 should include the following based outcomes.

	\begin{enumerate}
		\item Describe the major components of computer architecture; explain their purposes and interactions and the instruction execution cycle.
		\item Describe a basic instruction set architecture, including the arithmetic, logic, and control instructions; user and control registers; and addressing modes.
		\item Do simple arithmetic in hexadecimal, decimal, and binary notation, and convert among these notations.
		\item Explain how data types such as integers, characters, pointers, and floating point numbers are represented and used at the assembly level.
		\item Write C language programs that use control structures, functions, IO, arrays, and dynamic memory.
		\item Describe each step of the compilation process by which C language programs are transformed into machine code.  
		\item Explain how high-level programming constructs such as arrays, structures, loops, and stack-based function calls are implemented in  machine code. Recognize and reverse engineer same.
		\item Demonstrate and use a debugger to analyze program flow, inspect register and stack contents. 
		\item Identify and fix performance issues in C programs that are caused by machine level concepts.
		\item Explain how the information in this course is important within the overall context of computer science.
	\end{enumerate}

	\clearpage
	
	
	\section{CTF Activities}

	As mentioned above, implementations of CS205 are expected to use Capture The Flag style activities to develop hands on skills working with machine level code. Although Capture The Flag style activities derive from the cybersecurity community, the goal for these activities in this course is not the development of specific cybersecurity skills. Instead, their goal is to develop the skills necessary to inspect running machine-level code and the state of memory and understand what is going on. Those are the skills that serve as a foundation for future courses in operating systems, cybersecurity, compilers, embeded systems, and any other upper division work involving low level code.

	Similarly, while CTF originated as part of competitions where teams compete to solve a series of increasingly fiendish challenges, implementors of this course are explicitly encouraged NOT to utilize a competitive structure or focus on open-ended puzzles. Activities adopted from the CTF community should be modified to focus on pedagogical effectiveness instead of their utility for differentiating competing teams based on problem solving skills.

	Specific skills students are expected to develop are:

	\begin{enumerate}
		\item Use basic tools (e.g. objdump) to inspect compiled code.
		\item Read assembly in context and understand it. In particular, understand code generated by a compiler.
		\item Use a debugger (command line or visual) to inspect running code and memory.
	\end{enumerate}

	Sample activities:

	\begin{enumerate}
		\item Given a binary, use basic static analysis (objdump) to find a password or other information.
		\item Given a binary, use basic static analysis (objdump) to figure out the proper input to give to cause a desired output. 
		\item Given a binary, use a debugger to inspect it while running to figure out the proper input to cause a desired output. 
		\item Modify an executable with a hex editor (or running code with a debugger) to enable/disable functionality (change a branch target).
		\item Examine a program and engineer a basic buffer overflow on a stack based buffer to modify other local data or the return address. Or use a buffer to leak information about a running program. 
	\end{enumerate}

	More advanced CTF-style challenges likely go beyond the intended requirements of this course. This would include problems that involve: obfuscated code; detailed knowledge of OS constructs (user accounts); networking; buffer overflows that introduce new code; return oriented programming; or heap based exploits.

	\subsection*{PSU CTF Activities}

	Dr. Wu-chang Feng at PSU developed a web-based system, \url{https://oregonctf.org/}, for running CTF challenges and CTF style learning activities. A series of activities has been developed at PSU to support teaching their CS201. Each of these activity requires students to exercise skills to retrieve a password that is unique to them that verifies they completed the activity. So while students can help each with the techniques needed to solve each challenge, they cannot provide each other with answers.
	
	Dr. Feng and PSU have agreed to make the system available for schools implementing a CS205 to use. Schools can either:
	
	\begin{itemize}
		\item Host their own server using this docker image: \url{https://hub.docker.com/repository/docker/wuchangfeng/metactf}.
		\item Ask PSU to host a server as a subdomain at oregonctf.org. Contact wuchang@pdx.edu to set this up.
	\end{itemize}

	If you would like to test out the site, you can use \url{https://cs201.oregonctf.org} with the demo account credentials listed on the login page.

	The topic outline below lists relevant CTF activities from the PSU problem set under each section. 


	\section{CS205 Topic List}

	% \begin{longtable}{| p{0.5in} | p{6in} |} \hline
	% 	\rowcolor{lightgray}{\bf Wk} & {\bf Topic} \\ \hline \endhead
		
	% 	1 & Introduction to Systems \newline Intro to C for Systems  \\ \hline
	% 	2 & \href{https://web.cecs.pdx.edu/~markem/CS201/homework/MetaCTF/MetaCTF_description.html}{MetaCTF} overview and demo \newline The Compilation Process \newline Debugging Concepts   \\ \hline
	% 	3 & Data Representation \newline Arithmetic  \newline Base Types in C \\ \hline
	% 	4 & Floating Point \newline  C Functions \\ \hline
	% 	5 & Program Encodings / Data Formats \newline Arithmetic and Logical Operations \newline Stack-based buffer overflow attacks  \\ \hline
	% 	6 & Control \newline Procedures \\ \hline
	% 	7 & Pointers and Arrays  \\ \hline
	% 	8 & Structs, Unions, Alignment \newline Performance  \\ \hline
	% 	9 & Optimizations in C \newline  Dynamic Memory Allocation  \\ \hline
	% 	10 & Interrupts, Traps, and Exceptions \newline POSIX System Calls, Signals   \\ \hline
	% \end{longtable}
	

	The listed ordering of topics should in no way be considered prescriptive. While the topics listed below generally progress from fundamental to more advanced, any particular implementation of CS205 will likely find it advantageous to rearrange or crosscut topics. In particular, because this course covers both C programming and how C code runs on hardware, there are two possible approaches to teaching it: 1) focus on C programming before diving into assembly and how the code runs; 2) iterate through areas of C programming and how they are implemented. The topic list is structured in the later manner: it describes the expected boundaries for C and lower levels of each topic simultaneously. That should not be understood as precluding teaching the course by first focusing on C and then covering assembly/machine level topics.


	\subsection{Introduction to Systems}

	The fundamentals of computer systems and architecture that are critical for understanding assembly and high level performance concerns that are affected by architecture.

	\begin{enumerate}
		\item Fundamental components of a computer system and the fetch, decode, execute cycle.
		\item Memory hierarchy and role of caches. Detailed study of caches not required. Focus should be relative performance of different levels of the memory system and basic principles of cache management: block transfer and temporal and spatial locality. 
		\item Role of Operating System as hardware manager.
	\end{enumerate}

	\subsection{C Development Fundamentals}

	Writing and debugging a C program that does basic IO. Other topics in C programming are broken out with their assembly counterparts but could be taught with the fundamentals to make a larger initial module on C programming.

	\begin{enumerate}
		\item Role of C as portable assembly and high level language.
		\item Structure of a basic C program and use of basic IO and file instructions (fopen, printf, fgets, etc...).
		\item Compiling and running C code from the command line.
		\item Use of a debugger to examine running code at both the C and ASM level. Students should be familiar with setting breakpoints and examining the contents of registers and memory associated with symbols.
	\end{enumerate}
	
	\subsubsection*{Relevant PSU CTF(s)}

	Ch3\_00\_GdbIntro, Ch3\_00\_GdbPX, Ch3\_00\_GdbRegs


	\subsection{Compiling, Linking, and Loading}

	How C code is turned into object files and executables and the structure of those files. Across all of these areas, the focus is building the level of understanding important for a developer who will use C in future courses and who will be examining compiled code to understand it. Precise implementation details of any particular object format, linking process, etc... should not be an emphasis.

	\begin{enumerate}
		\item Compilation process - roles of: preprocessor, C compiler, assembler, linker. Individual components can be treated as black boxes, but students should recognize the kinds of errors messages that can result at each phase (linking vs compilation errors). 
		\item Basic structure of object files. Focus should be on understanding different segments and their roles.
		\item Symbols, symbol tables, and symbol resolution.  Emphasis should be on identifying and how symbols will be matched across object files/compilation units. 
		\item Relocation and position independent code. Again, focus should not be the details of any particular implementation, but on the kinds of transformations that happen as code is linked and loaded.
		\item Static vs dynamic linking. 
		\item Use of basic static inspection tools (e.g. objdump)
	\end{enumerate}

	\subsubsection*{Relevant PSU CTF(s)}

	Ch1\_LTrace, Ch1\_Readelf, Ch7\_13\_LdPreloadGetUID


	\subsection{Data Representation}

	How data is represented at a low level and how that shapes C programming. Understanding that these are determined by the architecture of the machine is critical - knowing the details of any particular architecture is not.

	\begin{enumerate}
		\item Binary, Decimal, and Hexadecimal representations. Converting from one form to another.
		\item Data sizes. Bytes and words as the fundamental unit sizes. 
		\item ASCII char representation.
		\item C integer data types and their sizes. Emphasis on platform dependence of these. 
		\item Enumerations.
		\item Machine instruction representation. How features like opcode, registers, and memory addresses are stored in an instruction.
		\item Endianess.
		\item Casting in C.
	\end{enumerate}

	\subsubsection*{Relevant PSU CTF(s)}

	Ch2\_01\_Endian, Ch2\_01\_Showkey, Ch2\_03\_IntOverflow, Ch3\_02\_AsciiInstr


	\subsection{Signed Arithmetic and Floating Point}

	How we do integer math in C and ASM and floating point math in C. (Coverage of floating point instruction in ASM is not required.) How negative and fractional values are represented at a binary level. 

	\begin{enumerate}
		\item Signed integer representation in 2s complement. Negation of signed values at the bit level. Recognition of important patterns (0xF...F is -1; a leading 1 is a negative number).
		\item Signed vs unsigned arithmetic. Overflow and its detection. When to use which format.
		\item Floating point representation. Memorization of a particular format is not required, but students should be exposed to an IEEE or IEEE-like format and understand the basic features of floating point representation: how representational resolution depends on magnitude, the existence of minimal/maximal representable values, and nan/infinity.
		\item The floating point types and their use in C. 
	\end{enumerate}
	
	\subsubsection*{Relevant PSU CTF(s)}

	Ch2\_03\_TwosComplement, Ch2\_05\_FloatConvert


	\subsection{Bitwise Operations}

	How to manipulate bits in ASM and C.

	\begin{enumerate}
		\item Bitwise logical operations and their use to manipulate individual bits.
		\item Shift/rotate operations.
		\item Use of shifts to multiply/divide binary values. The difference between arithmetic and logic shifts.
	\end{enumerate}
	
	\subsubsection*{Relevant PSU CTF(s)}

	Ch2\_03\_XorInt, Ch3\_05\_LorStr


	\subsection{Control Structures}

	C level control structures and their implementation at the ASM level.

	\begin{enumerate}
		\item Conditional structures (including switch) and loops in C.
		\item ASM comparison instructions and condition codes.
		\item ASM jump/branch instructions including conditional branches.
		\item Jump/branch tables.
		\item Implementation of C control structures in ASM.
	\end{enumerate}

	\subsubsection*{Relevant PSU CTF(s)}

	Ch3\_06\_SwitchTable

	\subsection{Memory and Pointers}

	How memory is accessed. Of critical importance is understanding the role of registers in the implementation of complex C expressions (or in all expressions for load/store architectures).

	\begin{enumerate}
		\item Pointers, addresses and dereferencing in C.
		\item ASM movement instructions using immediate values, registers, and memory.
		\item ASM addressing modes.
		\item The use of the stack to store data via ASM push/pop operations. How that stack is layed out in memory and how the stack pointer is used to maintain it.
	\end{enumerate}
	
	\subsubsection*{Relevant PSU CTF(s)}

	Ch3\_04\_FnPointer, Ch3\_04\_LinkedList


	\subsection{Dynamic Memory}

	Allocation/deallocation of memory in C and the standard memory model. Memory management in ASM would be an advanced week 10 extension.

	\begin{enumerate}
		\item Use of free/malloc in C.
		\item Heap vs stack. Strengths/weaknesses of allocations in each region.
		\item The "standard" process memory model (and how reality often is more complicated).
	\end{enumerate}


	\subsection{Functions}

	Functions in C and their implementation in assembly.

	\begin{enumerate}
		\item Functions in C.
		\item Pass by value vs reference.
		\item ASM level calling convention - how values are passed and returned.
		\item ASM implementation of local memory. Frame pointer and stack allocation/deallocation.
		\item Recursive functions - how the stack mechanism allows for reentrant code. 
	\end{enumerate}
	
	\subsubsection*{Relevant PSU CTF(s)}

	Ch3\_00\_GdbRegs, Ch3\_07\_ParamsRegs, Ch3\_07\_ParamsStack, Ch3\_07\_SegvBacktrace, Ch3\_07\_StaticStrcmp


	\subsection{Arrays and C-strings}

	Use of arrays and C-strings and working with arrays in ASM.

	\begin{enumerate}
		\item Array allocation (fixed and variable length) and use in C. 
		\item Multidimensional arrays in C.
		\item Pointer arithmetic and its relation to array indexing.
		\item Accessing individual array elements and looping through arrays in ASM.
		\item C-string related conventions and functions: NULL termination and basic string library functions.
		\item Stack based buffer overflow attacks.
	\end{enumerate}
	
	\subsubsection*{Relevant PSU CTF(s)}

	Ch3\_07\_CanaryBypass, Ch3\_07\_StackSmash, Ch3\_08\_Matrix


	\subsection{Heterogeneous Structures}

	Fundamental tools for grouping (possibly) heterogeneous data.

	\begin{enumerate}
		\item Structs.
		\item Unions.
		\item Data alignment and byte packing/padding in structures. 
	\end{enumerate}


	\subsection{Optimizations in C}

	Basic optimizations that compilers do related to concepts from this course. Exploring the effect of level optimizations in C code. (strength reductions, reducing procedure calls \& memory references, etc...). Coverage of this topic is not expected to be exhaustive - the goals are awareness of why compiled code often looks very different than what one would expect and how the kinds of low level efficiencies.

	\begin{enumerate}
		\item The kinds of optimizations that compilers routinely make (function inlining, dead store elimination) when compiling code.
		\item The effect of array stride order on performance.
		\item Relative performance of floating point and integer math - why we generally favor ints unless we need floating points.
		\item Basic performance optimizations available to high level language programmers: avoiding loop inefficiencies, reducing procedure calls and memory references, strength reductions.
	\end{enumerate}

	\subsubsection*{Relevant PSU CTF(s)}

	Ch5\_08\_LoopUnroll

	\clearpage
	\section{Sample Schedule}

	\begin{longtable}{| p{0.5in} | p{6in} |} \hline
		\rowcolor{lightgray}{\bf Wk} & {\bf Topic} \\ \hline \endhead
		
		1 & Introduction to Systems \newline C Fundamentals  \\ \hline
		2 & The Compilation Process \newline Object files \newline Data Representation  \\ \hline
		3 & Data Representation Continued  \newline  Arithmetic Operations  \newline Floating Point \\ \hline
		4 & Bitwise Operations \newline  Control Structures  \\ \hline
		5 & Memory and Pointers  \newline  Dynamic Memory Management \\ \hline
		6 & C Functions \newline  Implementation of Functions  \\ \hline
		7 & Arrays and C-Strings \\ \hline
		8 & Structs, Unions, Alignment \\ \hline
		9 & Performance \& Optimizations in C  \\ \hline
		10 & CS205 Topics in Context  \\ \hline
	\end{longtable}

	\clearpage
	\section{Week 10 Options}

	The tenth week of the course is designed to provide time for instructors to review critical material, finish up CTF work, and to expose students to applications of concepts from the course in the context of more advanced topics. While instructors are free to devise their own approach to doing so, three application areas are provided below as suggestions. For each, some resources are provided as a starting point.


	\subsection{Cybersecurity}

	Cybersecurity related knowledge and skills are undergoing a rapid increase in interest among students and employers. Many code level security topics depend directly on the knowledge and skills in this course. A deeper dive into cybersecurity related topics provides an opportunity to emphasize the practical CTF challenges and tease more advanced ideas like return oriented programming.

    \subsubsection{Reverse engineering}
    Reverse engineering of software is often done in a static fashion -- take a binary and pop it into a disassembler (\href{https://ghidra-sre.org/}{ghidra}, \href{https://cutter.re/}{Cutter (r2 or rizin)}, \href{https://www.hex-rays.com/products/ida/}{IDA}). This typically results in a listing of assembly code, either in list or call-graph form (sometimes both). Being able to read ASM, in any form, makes being able to reverse engineer software that much easier.

    A good in class exercise would be to take a program you know the structure of, and demonstrate how to reverse it using Cutter. Even better, take a lab that involved dynamic analysis (gdb bomb or similar) and redo the exercise statically.

    Having a sample binary to pop into Cutter here would be a good short HW -- have them write a description of what it does.

    \subsubsection{Firmware hacking}

    Most IoT devices aren't running x86 processors. Typically, they run some ARM variant, MIPS, or PPC. While this class doesn't cover those other architectures, knowledge of ASM is cross-functional. In other words, knowing ANY assembly language makes it easier to learn assembly language.

    A fun alternative to the above suggested homework is to do the same thing\ldots but with a binary from a MIPS or PPC system.

    \subsubsection{ROP}

    Exploit development nearly always has an assembly component. Even a simple buffer overflow requires some of the text being used to overflow the buffer to be written in ASM. This is known as shell code. One common approach to getting the shell code to run is to use a technique known as return oriented programming, or ROP. At a high level, ROP involves leveraging \texttt{ret}-like instructions to eventually cause a jump to an address you can control.

    A demonstration of a simple ROP chain would be a good in-class exercise, as well as talking about tools such as ropper or other similar gadget generation tools.

	\textcolor{red}{TODO - Kevin to provide a short outline.}

	\subsection{Operating Systems Programming}

	Students will generally go on to take an Operating Systems course that is very dependent on the skills developed in this course. Week 10 of CS205 is an opportunity to provide students with a consumer perspective on many of the topics they will study in depth in that OS course.
	
	\subsubsection{Exception Handling}
	\begin{enumerate}
		\item Exception number
		\item Exception table, aka, exception dispatch (jump) table, etc. ISA specific terminology.
		\item Exception handler. No discussion of up and bottom halves, just the basic concept.
	\end{enumerate}
		
	\subsubsection{System Calls -- OS As Privileged Service Provider}

	System calls are synchronous (traps). At the very least, there should be a detailed example of a simple C program making one or more system calls mapped down to assembly. The following exemplar is meant to be walked through line-by-line. This will help reinforce that system calls look just like function or library calls to the programmer. Modes will be introduced in the process discussion, below. The emphasis should be on POSIX-compliant system calls.
	
	\begin{enumerate}
		\item Processes and logical flow control.
		\item Concurrent Flows - basically about a gut feel for what it means for 2 processes to be concurrent.  This is a natural follow-on to exceptions and allows us to introduce the idea of a context switch.
		\item Process Address Space Layout
		\item User and Kernel Modes
		\item The Context Switch
		\item System Call Error Handling
		\item Process Control - fork/exec/wait
	\end{enumerate}

	\subsubsection*{Relevant PSU CTF(s)}

	Ch8\_05\_PsSignals, Ch8\_05\_Signals

	Resources:

	\begin{enumerate}
		\item Computer Systems - A Programmers's Perspective, Ch 8; Bryant and O'Hallaron
	\end{enumerate}
	
	\subsection{Data Oriented Design and Optimization in Games}

	While data oriented design and other optimizations are useful in any programming where performance is a high priority, for many computer users, video games are the most computationally expensive software packages run on a routine basis. They are a high interest place to explore the kinds of considerations that go into designing performant software. Topics including memory access in arrays and compiler optimizations can be reviewed and expanded on and more advanced topics like branch prediction can be teased.

	Resources:
	
	\begin{enumerate}

		\item The book Game Programming Patterns - available for free online: \url{https://gameprogrammingpatterns.com/}. Chapter 17 is likely the most relevant. Chapters 18-19 and 11 also of interest. Examples in the book are in basic C++.
	
		\item Game Engine Architecture, Jason Gregory. Chapter 3 is most relevant. \url{https://www.gameenginebook.com/toc.html}

		\item Seminal 2009 presentation by Tony Albrecht on optimizing for the PS3: 
		\url{http://harmful.cat-v.org/software/OO_programming/_pdf/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf}

		A 2017 followup talk by Tony Albrecht:
		\url{https://www.youtube.com/watch?v=VAT9E-M-PoE}


		\item Data Oriented Design in game development talk by Mike Acton: \url{https://www.youtube.com/watch?v=rX0ItVEVjHc}

		\item Data Oriented Design to make a faster HTML renderer: \url{https://www.youtube.com/watch?v=yy8jQgmhbAU}

		\item Matt Godbolt (of godbolt.org fame) on the cool magic that compilers do and why you should not assume you can out clever them with hand optimizations:
		\url{https://www.youtube.com/watch?v=w0sz5WbS5AM}

		\item Struct of Array vs Array of Struct organization: \url{https://medium.com/@savas/nomad-game-engine-part-4-3-aos-vs-soa-storage-5bec879aa38c} 
		
	\end{enumerate}

\end{document}