start ex2

Signed-off-by: Matt Strapp <matt@mattstrapp.net>

5 files changed, 302 insertions, 0 deletions

diff --git a/csci5271/hw2/animals b/csci5271/hw2/animals
new file mode 100644
index 0000000..e818860
--- /dev/null
+++ b/csci5271/hw2/animals
diff --git a/csci5271/hw2/ex2-animals.c b/csci5271/hw2/ex2-animals.c
new file mode 100644
index 0000000..983d2b5
--- /dev/null
+++ b/csci5271/hw2/ex2-animals.c
@@ -0,0 +1,131 @@
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef void (*toes_func)(void);
+
+void even_toes(void) {
+    printf("with even-toed hoofs");
+}
+
+void odd_toes(void) {
+    printf("with odd-toed hoofs");
+}
+
+/* Assume this function has the address 0x4012ce */
+void shellcode(void) {
+    printf("Uh-oh, this looks like some sort of attack\n");
+    exit(42);
+}
+
+struct herbivore {
+    struct herbivore *next;
+    toes_func func;
+};
+
+struct herbivore *herbivore_list = 0;
+
+struct carnivore {
+    struct carnivore *next;
+    long num_teeth;
+};
+
+struct carnivore *carnivore_list = 0;
+
+#define NUM_ANIMALS 256
+
+/* Initialized to all null pointers */
+void *animals_by_num[NUM_ANIMALS];
+
+void new_herbivore(long x) {
+    int loc = x & (NUM_ANIMALS - 1);
+    struct herbivore *hp = malloc(sizeof(struct herbivore));
+    printf("Allocating herbivore at %p\n", hp);
+    if (!hp)
+	exit(1);
+    if (x & 1)
+	hp->func = odd_toes;
+    else
+	hp->func = even_toes;
+    hp->next = herbivore_list;
+    herbivore_list = hp;
+    animals_by_num[loc] = hp;
+}
+
+void new_carnivore(long x) {
+    int loc = x & (NUM_ANIMALS - 1);
+    struct carnivore *cp = malloc(sizeof(struct carnivore));
+    printf("Allocating carnivore at %p\n", cp);
+    if (!cp)
+	exit(1);
+    cp->num_teeth = x;
+    cp->next = carnivore_list;
+    carnivore_list = cp;
+    animals_by_num[loc] = cp;
+}
+
+void release_animal(long x) {
+    int loc = x & (NUM_ANIMALS - 1);
+    if (!animals_by_num[loc]) {
+	fprintf(stderr, "Attempt to release non-existant animal\n");
+	exit(1);
+    }
+    free(animals_by_num[loc]);
+    animals_by_num[loc] = 0;
+}
+
+void list_animals(void) {
+    struct herbivore *hp;
+    struct carnivore *cp;
+    for (hp = herbivore_list; hp; hp = hp->next) {
+	printf("A herbivore ");
+	(hp->func)();
+	printf("\n");
+    }
+
+    for (cp = carnivore_list; cp; cp = cp->next) {
+	printf("A carnivore with %ld teeth\n", cp->num_teeth);
+    }
+}
+
+void syntax_error(void) {
+    fprintf(stderr, "Unrecognized syntax\n");
+    exit(1);
+}
+
+int main(int argc, char **argv) {
+    for (;;) {
+	int c = getchar();
+	long x;
+	while (isspace(c))
+	    c = getchar();
+	if (c == EOF)
+	    return 0;
+	switch (c) {
+	case 'h':
+	    if (scanf(" %li", &x) != 1)
+		syntax_error();
+	    new_herbivore(x);
+	    break;
+	case 'c':
+	    if (scanf(" %li", &x) != 1)
+		syntax_error();
+	    new_carnivore(x);
+	    break;
+	case 'r':
+	    if (scanf(" %li", &x) != 1)
+		syntax_error();
+	    release_animal(x);
+	    break;
+	case 'l':
+	    list_animals();
+	    break;
+	case 'q':
+	    return 0;
+	    break;
+	default:
+	    fprintf(stderr, "Unrecognized command %c\n", c);
+	    exit(1);
+	}
+    }
+}
diff --git a/csci5271/hw2/ex2-template.tex b/csci5271/hw2/ex2-template.tex
new file mode 100644
index 0000000..96eca28
--- /dev/null
+++ b/csci5271/hw2/ex2-template.tex
@@ -0,0 +1,68 @@
+\documentclass[11pt]{article}
+\usepackage{fullpage}\usepackage{listings}
+\usepackage{times}
+
+\begin{document}
+\begin{center}
+CSci 5271 Fall 2021 Exercise Set 2 answers template
+\end{center}
+
+Please use this as a template for submitting your answers to
+exercise set 2. (This template is available from the course web site
+in either LaTeX or Google Doc formats). Type your answers on each page
+after the question prompt (you can use additional pages, though that
+we expect that would rarely be required). If you can write all your
+answers electronically, please do so and export to a PDF to submit.
+If you would prefer to hand-draw figures, you can also submit a scan.
+
+Please ensure that the names and UMN email addresses of all of your
+group members are recorded on Gradescope, and also confirm them below:
+
+\vspace{10pt}
+
+\begin{tabular}{|p{2.6in}|p{2.6in}|}\hline
+Name & UMN email address\\\hline
+Matt Strapp & strap012@umn.edu \\\hline
+\end{tabular}
+
+\vspace{10pt}
+
+Question 1 (buffer overflows and invariants, 25 pts):
+
+Example input that causes a buffer overflow:
+\begin{verbatim}
+    "{}{}{}{}{}{}{}{}{}{}"
+\end{verbatim}
+
+A list of invariants for the transform function:
+\begin{itemize}
+    \item bp is increased by one for every opening brace or bracket and goes down by one for every closing brace or bracket. (this gets violated)
+    \item 
+\end{itemize}
+The change that needs to be made is to make sure that bp decrements when there is an opening curly brace regardless of the rotate amount.
+
+\newpage
+
+Question 2 (a heap-related vulnerability, 20 pts):
+\begin{verbatim}
+    "h 0x4012ce r 0x4012ce c 0x4012ce l" 
+    //(all of those commands are separated by \n)
+\end{verbatim}
+
+This code is an example of a use-after-free exploit. The way this exploit works is first the program allocates the herbivore with 0x4012ce hooves and is immediately freed. A carnivore is then created with the same address as the previously freed herbivore. The \verb|l| then reads the previously freed herbivore's hooves value as a function and it executes herbivore's toe count as a function, which was set to the address of \verb|shellcode()|.
+\newpage
+
+Question 3 (reference monitor without hardware support, 15 pts):
+
+\newpage
+
+Question 4 (sharing files on Unix, 20 pts):
+
+The program does not check that the user is supposed to write the output file in read or read the input file in write, allowing potentially arbitrary read/write privileges. This can be solved by implementing that check.
+The list of users with access would need to be updated frequently to ensure that someone properly loses access. A possible mitigation problem would be automating actively updating the list of users with and without access but that might not be possible.
+The program also implies that the user running the program is actually the real user and not someone impersonating them. The problem with impersonating could be solved with passwords but those can be cracked.
+\newpage
+
+Question 5 (Multilevel-secure classification, 20 pts):
+
+\end{document}
diff --git a/csci5271/hw2/ex2-transform.c b/csci5271/hw2/ex2-transform.c
new file mode 100644
index 0000000..b857042
--- /dev/null
+++ b/csci5271/hw2/ex2-transform.c
@@ -0,0 +1,103 @@
+#include <assert.h>
+#include <stdio.h>
+#include <ctype.h>
+
+char rot_char(char c, int amt) {
+    if (c >= 'A' && c <= 'Z')
+        return 'A' + ((c - 'A') + amt) % 26;
+    else if (c >= 'a' && c <= 'z')
+        return 'a' + ((c - 'a') + amt) % 26;
+    else
+        return c;
+}
+
+void transform(char *inputBuffer, char *outputBuffer, int inLimit) {
+    char *inputPointer = inputBuffer;
+    char *outputPointer = outputBuffer;
+    char *outLimit = &outputBuffer[inLimit - 8];
+    char c;
+    int in_underline, last_underline, rotate_amount, skipping;
+    int bracket_level, brace_lvl;
+    in_underline = bracket_level = brace_lvl = last_underline = rotate_amount = skipping = 0;
+    
+    while ((c = *inputPointer++) != '\0') {
+        if (bracket_level > 0)
+            c = toupper(c);
+
+        c = rot_char(c, rotate_amount);
+
+        if (c == '/')
+            in_underline = !in_underline;
+
+        skipping = (outputPointer >= outLimit);
+        if ((unsigned)c - (unsigned)'[' < 3u && c != '\\') {
+            int i = (c & 2) ? 1 : -1;
+            if (bracket_level + i >= 0 && !skipping) {
+                bracket_level += i;
+                outLimit -= i;
+            }
+        }
+
+        if (c == '{') {
+            if (!skipping) {
+                brace_lvl++;
+            }
+            rotate_amount += 13;
+            if (rotate_amount == 26) {
+                rotate_amount = 0;
+                outLimit -= 2;
+            }
+        }
+        if (c == '}' && brace_lvl > 0) {
+            if (!skipping) {
+                brace_lvl--;
+                outLimit++;
+            }
+            rotate_amount -= 13;
+            if (rotate_amount < 0)
+                rotate_amount = 0;
+        }
+
+        if (in_underline && isalpha(c) && !last_underline && !skipping)
+            *outputPointer++ = '_';
+
+        if (c != '/' && !skipping)
+            *outputPointer++ = c;
+
+        if (in_underline && isalpha(c)) {
+            if (!skipping)
+                *outputPointer++ = '_';
+            last_underline = 1;
+        } else {
+            last_underline = 0;
+        }
+    }
+    while (bracket_level-- > 0)
+        *outputPointer++ = ']';
+    while (brace_lvl-- > 0)
+        *outputPointer++ = '}';
+    *outputPointer++ = ' ';
+    *outputPointer++ = 'e';
+    *outputPointer++ = 'n';
+    *outputPointer++ = 'd';
+    *outputPointer++ = '\0';
+}
+
+int main(int argc, char **argv) {
+    char buf[64];
+    if (argc != 2) {
+        fprintf(stderr, "Usage: transform <string>\n");
+        fprintf(stderr, "You should probably use quotes around the string.\n");
+        return 1;
+    }
+    printf("%s\n", argv[1]);
+    buf[20] = '\242';
+    transform(argv[1], buf, 20);
+    printf("%s\n", buf);
+    /* This canary-like check isn't foolproof, and it isn't the point
+       of the exercise, but for testing purposes it makes it easy to
+       see that an overflow has happened. */
+    if (buf[20] != '\242')
+        fprintf(stderr, "Overflow detected\n");
+    return 0;
+}
diff --git a/csci5271/hw2/transform b/csci5271/hw2/transform
new file mode 100644
index 0000000..bffc858
--- /dev/null
+++ b/csci5271/hw2/transform