start ex2

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

6 files changed, 411 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
diff --git a/papers/3606midtern.tex b/papers/3606midtern.tex
new file mode 100644
index 0000000..5a6bea3
--- /dev/null
+++ b/papers/3606midtern.tex
@@ -0,0 +1,109 @@
+\documentclass[12pt]{article}
+\usepackage{setspace}\doublespacing\usepackage{indentfirst}
+\usepackage[left=1in,right=1in,top=1in,bottom=1in]{geometry}
+\pagenumbering{gobble}
+\begin{document}
+Throughout the era shortly after the Arab Conquests, Christians and Jews were allowed special privileges not granted to other nonbelievers.
+For these protections, they were required to follow numerous restrictions.
+These restrictions were implemented differently throughout the Muslim world.
+Some leaders would enforce every rule and even revoke \emph{dhimmi} status, while others would be more lenient.
+
+Christians and Jews in Muslim lands were subject to many requirements to be classified as \emph{dhimmi}.
+The \emph{dhimmi} had to provide food to any Muslims that pass by their way and keep their gates open for travelers.
+They could not hold any public religious ceremonies nor attempt to convert any Muslims.
+Non-Muslims were also not allowed to dress like Muslims and had to wear a distinctive zunnar.
+They were forbidden from carrying weapons and riding on horses.
+Their homes could not be built taller than any Muslim's home.
+(Pact of Umar-version 1) \emph{Dhimmi} were not allowed to marry a Muslim.
+They were completely forbidden from entering Mecca.
+Christians and Jews were not allowed to use the main roads, those were exclusively for Muslim use.
+They were not allowed to display alcohol or pigs, which were forbidden under Muslim law.
+(The Regulation of \emph{Dhimmis}) Most importantly, they were required to pay an annual tax, the \emph{jizya}.
+The \emph{jizya} was a requirement for all adults to pay.
+If they did not pay, they were not protected. (Pact of Umar-version 2)
+The protections were granted to all Christians and Jews in Muslim lands.
+
+In return for following all of those requirements, those labelled \emph{dhimmi} were not required to convert to Islam.
+This was a special privilege granted only to them.
+Other religions in conquered lands were either forced to convert to Islam or were executed.
+They were given many of the same protections that Muslims were granted: ``We will protect you and your lawful (according to our law) property against any one, Muslim or not, who tries to wrong you, as we protect ourselves and our own property'' (Pact of Umar-version 2).
+This protection was not extended to things forbidden by Islamic law, which included pork and any alcoholic beverage.
+The exchange of rights for protections meant that the \emph{dhimmi} were largely treated as second class citizens compared to Muslims.
+
+These protections were designed in the early Islamic world.
+Muhammad himself encouraged some of his followers to learn the languages of foreigners (Tannous, \emph{The Making}, 415).
+These early Muslims would read older religious scripture and connect Muhammad's teachings with the teachings of old.
+Many of the rules that were eventually codified into the Pact of Umar were created during the era shortly after the Arab Conquests through \emph{hadith}.
+After the death of Muhammad and the fall of the Rashidun Caliphate, the successor states were different.
+
+Different rulers had different opinions on the status of \emph{dhimmi} and what to do with them.
+Caliph al-Mutawakkil would enforce the Pact of Umar by ordering all new churches and synagogues to be torn down (Cohen, 164).
+All non-Muslims were expelled from the Hejaz, the area around the holy cities of Mecca and Medina.
+The Almohads of North Africa would force all nonbelievers to either convert or be put to death.
+The Jews in Yemen were also forced to convert or die.
+Many of these persecutions were exceptions to the overall status of the protected classes.
+In many places, Christians and Jews were largely treated as equals.
+Many of the rules about buildings and clothing requirements were largely ignored (Instruction to a Market Inspector).
+Many Islamic judges ruled that the \emph{dhimmi} had a right to reside in Muslim lands and that their property should be protected (Cohen, 166--168).
+These uneven restrictions would persist throughout the Muslim world.
+
+Muslim leaders from modern-day Spain to Iran had different opinions and ideas on the status of \emph{dhimmi}.
+While they were theoretically protected second class citizens, this was enforced differently in different places.
+Some were forced to convert or expelled, while others were allowed to do as they pleased provided they pay the \emph{jizya}.
+This largely remained unchanged until much of the Muslim world secularized in modern times.
+
+\pagebreak
+
+\begin{center}
+    \emph{Letter}
+\end{center}
+
+Cousin, I thank you for the letter and wish you and your family the best of luck in your future endeavors.
+I hope this letter comes back to you in good health.
+
+Jerusalem has changed over the years.
+My father once heard from his father was once a peaceful, quiet city.
+My grandfather was alive when the Muslims conquered the city.
+He has told us stories about the times before the Arabs where we were allowed to do as we pleased.
+This has changed since the Muslims conquered the area.
+We now have to follow their rules.
+Those who did not were expelled or forced to submit to Islam.
+My grandfather personally knows some people who lived in the city for centuries who were forced to leave because they refused to follow the rules placed upon us.
+
+Since the conquest, the city has become more active.
+The Muslim Dome definitely does exist, I can see if from the distance when I walk in the city.
+I have personally not been there myself but some of the Muslims my family trade with describe it as a beautiful monument and a piece of art.
+My father said that when it was being build he had never seen so many people in the city before.
+
+Why it was built, I do not know.
+Members of my church deride the building as yet another display of Muslim conquests and the glory of their God.
+Others have stated that it is a reply to the beauty of Christian churches.
+The building itself is prominent in the city and if your message is true has become its symbol.
+If so the Muslim identity has taken over the city's Christian roots.
+
+As long as we pay the \emph{jizya}, the Muslims have agreed to protect us and allow us to worship the Trinity.
+So far they have kept to their oath but few trust that they will always keep to their word.
+They have forbidden us from praying and spreading the word of Christ in the streets.
+They have also forbidden us from loudly praying during church sessions, including forbidding the use of our clappers.
+We also have to wear crosses when out in the city.
+We now have to eat pork and drink alcohol in secret.
+If any Muslim official sees it we are forced to get rid of it.
+Many fear that we will be driven out of the city soon.
+Some also fear that we will be forced to convert to Islam.
+I pray that this never happens.
+My family and I have been here for generations.
+I pray that God will not let us down.
+
+Their new mosque has also become a new major landmark in the city.
+Five times a day there is a prayer in the mosque.
+At those times there is a loud cry out for prayer.
+This prayer stops the city for a brief period of time.
+The outside of the building looks almost as beautiful as our churches.
+Non-Muslims have not been allowed in the building but from what Muslims have said it is beautiful.
+Pilgrims and other travelers have also stated that the Muslims have torn down churches in other areas they have conquered.
+I pray that they do not do that, for they know the city is important to more than them.
+
+Cousin, please pray that God will protect us.
+The Muslims have been protecting us for now but no one knows how long that might last.
+I pray that we will be able to preserve the beauty of the holy city for all Christians.
+\end{document}
\ No newline at end of file