DIY Network-based IDS: A Tutorial Introduction Now that you have hooked syscalls for an operating system, you have essentially created a sandbox to run malicious code in! These are crucial for setting up a network-based intrusion detection system as you are now able to inspect every executable that flows through your network. All you need to do is hook it up and automate the process! Simple, right? ● Install Vagrant ● Download the Vagrantfile for this project here (it can also be found under the Files tab in Canvas): https://gatech.instructure.com/files/20628443/download?download_frd=1 ● Make sure you have VirtualBox or one of the other provider s installed ● Initialize your environment by first cd-ing into the directory with the Vagrantfile (hopefully its own directory for your lab), and typing vagrant up into your command line● This will set up 3 different machines which are all headless. You can enter them by typing (sudo) vagrant ssh [hostname]: ○ mal: the ‘malicious’ machine, that sends malicious binaries over the network. The client vicky will attempt to receive from mal. ■ Username/password: vagrant/vagrant ■ Home: /home/mal/ ■ Utilities already installed: vsftpd ■ IP: 192.168.50.2 ○ vicky: the ‘victim’ machine that will receive the files from mal. For every executable file downloaded from mal, vicky will need to forward the Snort log/PCAP file to sandy. ■ Username/password: vagrant/vagrant ■ Utilities already installed: vsftpd, snort (and dependencies), git, python, watchdog, pwn ■ IP: 192.168.50.3 ○ Sandy: the ‘sandbox’ machine, which is basically the starting OVA from Lab3. It drops all packets to mal to simulate the box being isolated from the outside. It will receive the executables from vicky and run them to check if they are malicious or benign. Then, it will need to record the alert in /var/log/ids_alert.log ■ Username/password: lab3/captainhook ■ Utilities newly installed: vsftpd ■ IP: 192.168.50.410pts The first part is to confirm that vicky is able to receive a file from mal. For that, you will have to SSH into mal and try to connect to vicky via the FTP protocol. You can do this by typing $ ftp [IP] and following the prompts to send a file (you can log in using the username and passwords below). The manpage for vsftpd is found here: https://help.ubuntu.com/community/vsftpd. 20pts Note: among the provided samples, there is only one sample that does not contain executable file. Your Snort rule should not trap the file. 20pts Then, you will want to write an automatic process that will send the log file create over to sandy (best if over FTP) any time there is a new log file created. One way to do this can be with the use of a daemon, and you can find a tutorial here: http://shahmirj.com/blog/beginners-guide-to-creating-adaemon-in-linux. This can also be done as a shell script. Make sure you do not send the same log twice! 30pts Part 3a – Now, your work will be in sandy. You will have to tweak your current script somewhat so it is no longer an anomaly detection engine: it will solely be used to detect malicious syscalls (the same syscalls identified in the last project) and print them to the kernel log. This should be a simple copy-paste. If you do not wish to use your script from lab3, we are also providing a sample hooks.c script with all the hooks you might need for this assignment, which can be found here (it can also be found under the Files tab in Canvas). Part 3b – The next step is to write a daemon for sandy such that whenever it receives a new log (hopefully always to the same directory), it will extract the binary from the PCAP and run the binary (with the LKM already inserted). 10pts Today, while syslogd, the syslog daemon, manages some of the logging in Ubuntu, most of it is done through a service called rsyslogd, which extends the functionality of syslog (incidentally, extending it to log kernel messages). This service is also configurable, so you are able to direct messages to different log files of your choosing (even new ones!). You will need to configure rsyslogd so that it will output any messages from your LKM to be put into a log file called ids_alerts.log. The full documentation for this can be found here: https://www.rsyslog.com/doc/v8-stable/configuration/index.htmlBonus – 5 pts + 5 pts Part a – you will have to think of what potential behaviors malicious binaries might have. You will alert these behaviors in the rsyslog. Then, after analyzing the resyslog, Sandy will transfer back the benign files to client Vicky and drop the malicious files. Part b – Zeek (or originally called Bro) is an alternative network IDS tool for snort. For this part, you will use Zeek for Part 1 as an alternative of snort on the detection of the executable files sent over the network. Similar to snort, you will have to log the binary drop and extract the executable file. Deliverables ● Zip the following files in a .tar.gz file called [GTusername]_cs6264_lab5.tar.gz ○ Snort configuration ○ Various daemons that you wrote for both the sandbox and the client ○ Your LKM C file and Makefile ○ The new rsyslog configuration ● A report of your NIDS that includes: ○ Screenshots of each step of the process from when you send the file to the client to when an alert is logged. These should probably include: sending the executable from mal; receiving the executable in vicky; sending the PCAP to sandy; the sandbox alerting/not alerting on the executable ○ Any implementation details that you want to share Rubrics ● Proof of successful file transfer over FTP: 10 pts Snort rule correctly written: 20 pts Daemon to send file from Vicky to Sandy correctly written: 20 pts LKM updated for new malicious program: 10 pts Daemon written to analyze program on sandy: 20 pts Rsyslogd config correctly written: 10 pts ● Report: 10 pts ● Bonus: 10 pts
CS 6264-OCY: Lab 3 Rooting an Android DeviceDisclaimer: This lab was adapted from the Android Device Rooting Lab from the SEED Labs project.Introduction Android devices do not allow their owners to have the root privilege on the device. This is fine for normal customers, but for users who want to make deep customizations on their devices, this is too restrictive. There are ways to overcome these restrictions, most of which require the root privilege on the device. The process of gaining the root device on Android devices is called rooting. Being able to root Android devices is a very useful skill for security experts. The objective of this lab is three-fold. First, through this lab, students will get familiar with the process of device rooting and understand why certain steps are needed. Many people can root Android devices, but not many people fully understand why things have to be done in a particular way. Second, the entire rooting mechanism involves many pieces of knowledge about the Android system and operating system in general, so it serves as a great vehicle for students to gain such in-depth system knowledge. In this lab, we will ask students to develop a complete rooting package from scratch and demonstrate how to use the package to root the Android VM provided by us. Third, to get a better understanding of how dangerous granting root access to unknown applications is, we will also ask students to implement a simple location app that can leverage root access and get user location without permission. Background Knowledge Background Knowledge about Rooting The purpose of rooting an Android device is to gain the root privilege inside the Android OS. There are many reasons why people want to do that. For example, Android devices often come with many preinstalled system apps that are useless most of the time, but they take storage space, RAM, system resources, and drain device battery. These useless apps are generally known as bloatware; they are installed in protected places, and only the root user (or other privileged user) can remove them. Although the device is owned by a user, the user is not allowed to run code using the root privilege. Users can only get the root privilege if the device is rooted. In general, rooting allows users to customize their phones, removing restrictions, adding new features, and making changes to the system. There are several approaches to root an Android device, and we will discuss them in more detail in this lab. Figure 1 provides a summary of these approaches. In the past, there were many rooting exploits, such as RageAgainstTheCage, which took advantage of RLIMIT_NPROC max, the value specifying how many processes a given UID can run. This exploit first uses “adb shell” to run a shell on the device via the adb daemon. The UID of the shell will be 2000. The exploit then forks new processes until the number of processes have reached the limit and the fork call will fail. At this point, the exploit kills the adbd daemon, and then reconnect to it using “adb shell”. This causes the system to restart the adb daemon. When adb is started, it always has the root privilege, but it will drop the privilege to UID 2000 using setuid(2000). Unfortunately, the UID 2000 has already used up its process quota, so the call will fail. Unfortunately, the adb daemon fails to handle the failure correctly: instead of exiting, it keeps running, while retaining the root privilege. As results, the “adb shell” command will give users a root shell. This vulnerability has already been fixed after Android 2.2.Figure 1. Rooting Android Devices. Modifying Android from outside. Since Android’s access control prevents a normal user from modifying the part of the system that is only modifiable by the root, doing it inside Android is going to subject to the access control. However, if we can do it from outside, we are not subject to Android’s access control anymore. This leads to the second approach, which is to directly modify Android’s system files from outside. Assume that another operating system is installed on your Android device. This means that the device has a dual-boot configuration, allowing you to boot into any of these two operating systems when the device powers on. If we boot into this second operating system, and become the root for this OS, we can mount the partition used by the Android system. Once this partition is mounted, we can access all the files stored inside the partition. Because Android is not running, its access control has no use. Therefore, we can make arbitrary changes to its files. For example, we can place some programs in the system, and modify Android’s initialization scripts, and ask Android to run our programs as a root during its initialization process. The good news is that most Android devices do have the second operating system installed, and it is called recovery OS. As the name indicates, it is meant for recovery purposes, but it is mostly used for updating operating system. The bad news is that this operating system also has access controls, preventing users from running arbitrary programs or commands. Recovery OS is typically placed on devices by vendors, who use the OS to update Android, but not wanting users to make arbitrary updates. To enforce that, recovery OSes do not give users a shell prompt, preventing users from running arbitrary commands. Instead, they take a package provided from outside (either from users or downloaded from the Internet); the package contains the commands and files needed for updating the Android OS. This mechanism is widely used for OS update, and it is called Over-The-Air (OTA) update. The package is called OTA package, which has a standard file structure that we will talk about later. Most recovery OSes only accept the packages made by the vendors to ensure that any update to the Android OS is approved by the vendors. This is enforced using digital signatures, i.e., the package needs to be signed by vendors, or it will not be accepted by the recovery OS. This protection becomes a roadblock for rooting, because the package that we use for rooting purposes will not come from the vendor of the device. We need to find ways to bypass this access control. Reinstall recovery OS. Instead of bypassing the access controls of the recovery OS, the easiest way is to replace the entire stock recovery OS with another recovery OS that does not have such access controls. This new recovery OS, called custom recovery OS, will not include the signature verification part, so we can provide any OTA packages to the recovery OS. This will allow us to make arbitrary changes to the Android partition. Here is another bad news. There is another access control that prevents us from replacing the stock recovery OS, and this time it is the bootloader. Bootloader is a low-level code that loads an operating system or some other system software for the computer after the computer is powered on. When a bootloader is “locked”, it will simply load one of the OSes that is already installed on the device, leaving no chances for users to modify any of the pre-installed OSes. If a bootloader can be unlocked, it will add another option, which allows users to install custom operating systems on the device, as well as replacing the existing ones. The process is often referred to as flashing custom OS. Manufacturers usually make their bootloaders locked out of the box because they want to be in control of what software is running the device. However, most manufacturers do provide ways for users to unlock the bootloader on their devices, provided that by doing so users will lose all of their data, as well as the warranties. Background Knowledge about OTA OTA is a standard technique for devices to update Android operating systems. Since rooting also needs to update Android OS, OTA becomes a popular choice. In this section, we will describe the structure of the OTA package. Students need to build their own OTA package from the scratch in this lab. OTA package is just a zip file and its structure is depicted in Figure 2. Of particular interest to this lab is the META-INF folder, which includes signature and certificates of the package along with two very important files named update-binary and updater-script.Figure 2. OTA Structure ● META-INF/com/google/android/update-binary: This binary is executed by the recovery OS to apply OTA updates; it loads and execute updater-script. ● META-INF/com/google/android/updater-script: This is an installation script which is interpreted by update-binary. It is written using a script language called Edify, which describes the required action to be performed to apply updates.After signature verification on the OTA package, the recovery OS extracts the update-binary executable from the OTA package to the /tmp directory and runs it by passing three arguments as follows: update-binary version output package where, version is the version of recovery API, output is the command pipe that update-binary uses to communicate with recovery, package is the path of the OTA package, An Example would be: update-binary 3 stdout /sdcard/ota.zip On a successful execution of updater-script, the recovery OS copies the execution logs to the /cache/recovery/ directory and reboots into the Android OS. Execution logs can be accessible from the Android OS after rebooting. This is how android system is updated by using OTA package. Lab Environment In this lab, we assume that the bootloader on the device can be unlocked, and the stock recovery OS can be replaced. Replacing the recovery OS in the VM environment is quite difficult, and it is not within the scope of this lab. The Android VM that you download from this website already has a custom recovery OS installed. Actually, we simply use Ubuntu 16.04 as the “recovery OS”. Technically, this is not a recovery OS; it is just another OS installed on the device. We use this general-purpose OS to emulate what users can do using a custom recovery OS. Once users boot into this OS, they can run any arbitrary commands (as root) and be able to make arbitrary changes to the Android partition. Students who have a physical Android device and want to know how to root a real device, they can follow our guidelines in the Guidelines section. However, other than the step to replace the recovery OS, everything else is the same as what we do in this lab. Another important thing to know is that our Android VM is already rooted. That was done when we built the VM from the Android source code. Our VM build is actually a userdebug build, and several doors were built into the VM to allow root access. We choose this build because several of our other labs require the root access. Real Android devices use user build, which do not have these doors for root access. Details about these doors can be found in our VM manual. In this lab, students are not allowed to use those doors to gain the root access; they have to use the OTA mechanism to achieve that. We also provide an Ubuntu VM to compile the required code and set up the OTA mechanism. This is provided in the .vmdk file format. To get started, all you need to do is start a new VM as you usually would in VirtualBox, choose Ubuntu 32-bit as the operating system, and once you get to defining a hard disk for the VM, choose the .vmdk file instead of creating a new virtual hard disk. The credentials for this VM are: seed/dees.Part 1: Task 1: Build a simple OTA package In this lab, students will build a simple OTA package from scratch, and use it to root Android OS. We divide this complicated task into several tasks, each focusing on a specific goal. Here are the goals that we would like to achieve: ● How to inject a program into the Android OS from the recovery OS? ● How to get our injected program to run automatically, and with the root privilege? ● How to write a program that can give us the root shell? In this Task 1, we focus on how to inject a program into the Android OS from the recovery OS, and then get Android to run our injected program using the root privilege. At this point, we are not focusing on the actual thing that we can do in this program, as long as it is something that requires the root privilege. For the sake of simplicity, let us simply create a dummy file in the /system folder of Android, which requires the root privilege (the /system folder is not writable by normal users). The following command puts a word “hello” in /system/dummy (we put this command in a shell script file called dummy.sh): echo hello > /system/dummy Step 1: Write the update script. The update-binary file in the OTA package is the executable file that will be first executed by the recovery OS. This is where we get the OS update started. This file can be a binary executable, or just a simple script file. For the latter case, the recovery OS should already have the binary executable (e.g. bash) to execute the script file. In this task, we will simply use a shell script, as our recovery OS (Ubuntu) does have bash installed. Our purpose for update-binary is two-fold: (1) inject our dummy.sh program into the Android OS, and (2) change the Android OS configuration file, so our dummy.sh can be automatically executed with the root privilege when Android boots up. For the first task, students need to figure out where to place dummy.sh, and how to set up its permissions. It should be noted that the file has to be placed into the Android partition, which is already mounted to the /android directory in the recovery OS. For the second purpose, we need to get dummy.sh to run automatically when Android boots up, and we need to make sure that it runs with the root privilege. There are many ways to achieve this. In this task, we use one approach related to Linux, and in the next task, we will use a different approach related to Android framework. Android is built on top of the Linux operating system. When it boots up, its underlying Linux boots up first, which conducts system initialization, including starting essential daemon processes. The booting procedure, using the root privilege, runs a file called /system/etc/init.sh for part of the initialization. Therefore, if we can insert a command into init.sh file, we can run our dummy.sh file with the root privilege. If we can do it manually, we can simply edit the init.sh, and add a new command in it, but we are writing an OTA package, so the actions to modify the file need to be coded in our update-binary file. There are many ways to code that, and we will use the sed command, which is stream editor forfiltering and transforming text. Our idea is to find where the statement “return 0” is inside init.sh, and insert a command before that, essentially placing the command before the program in init.sh finishes. sed -i “/return 0/i /system/xbin/dummy.sh” /android/system/etc/init.sh Explanation: ● “-i”: edit files in place. ● “/return 0/”: match the line that has the content return 0. ● “i”: insert before the matching line. ● “/system/xbin/dummy.sh”: the content to be inserted. We need to copy the dummy.sh file to the corresponding folder first. ● “/android/system/etc/init.sh”: the target file modified by “sed”. Step 2: Build the OTA Package. Constructing an OTA package is quite straightforward. All we need to do is to put our files in their corresponding folders according to Figure 2. We need to maintain the same structure as what is shown in the figure, but you do not need to create all the files that are not needed for our task (such as signature and optional files). You can put the dummy.sh file in any place of your OTA package, as long as the location matches with your command in the update-binary. After creating the file structure, we can use the zip command to create a zip file: zip -r my_ota.zip ./ You should include the file structure of your OTA package in your report. You can run the “unzip -l” command to do that. Step 3: Run the OTA Package. After building the OTA package, we can provide it to the recovery OS, which will run it automatically. However, that is how it works with a real recovery OS. In our lab environment, we are using Ubuntu as our recovery OS, but it does not have the needed recovery functionality. Therefore, we have to emulate the recovery functionality. This means, we have to manually unpack the OTA package (using the unzip command), go to the folder META-INF/com/google/android folder to find the update-binary file, and run it. If you have written everything correctly, your Android is now updated. Now, boot up your Android OS, and see whether the dummy file is created inside /system. In your report, you should include screenshots to provide evidences. Task 2: Inject code via app_process In the previous task, we modify the init.sh file to get our injected program to run automatically, and with the root privilege. This initialization script file is used by the underlying Linux operating system. Once the Linux part is initialized, Android OS will bootstrap its runtime that is built on top of Linux. We would like to execute our injected program during this bootstrapping process. The objective of this task is not only to find a different way to do what we have done in the previous task, but also to learn how Android gets bootstrapped. Before conducting this task, please read the guideline in Section 7.1 about the Android booting sequence. From the guideline, we can see that when the Android runtime bootstraps, it always runs a program called app_process, using the root privilege. This starts the Zygote daemon, whose mission is to launch applications. This means that Zygote is the parent of all app processes. Our goal is to modify app_process, so in addition to launching the Zygote daemon, it also runs something of our choice. Similar to the previous task, we want to put a dummy file (dummy2) in the /system folder to demonstrate that we can run our program with the root privilege. The following sample code is a wrapper for the original app_process. We will rename the original app_process binary to app_process_original, and call our wrapper program app process. In our wrapper, we first write something to the dummy file, and then invoke the original app_process program. #include #include #include extern char** environ;int main(int argc, char** argv) { //Write the dummy file FILE* f = fopen(“/system/dummy2”, “w”); if (f == NULL) { printf(“Permission Denied. ”); exit(EXIT_FAILURE); } fclose(f);//Launch the original binary char* cmd = “/system/bin/app_process_original”; execve(cmd, argv, environ);//execve() returns only if it fails return EXIT_FAILURE; } It should be noted that when launching the original app_process binary using execve(), we should pass all the original arguments (the argv array) and environment variables (environ) to it. Step 1. Compile the code. We need to compile the above code in our SEEDUbuntu virtual machine, not inside the recovery OS or Android OS, as neither of them has the native code development environment installed; we have installed the Native Development Kit (NDK) in our SEEDUbuntu VM. NDK is a set of tools that allow us to compile C and C++ code for Android OS. This type of code, called native code, can either be a stand-alone native program, or invoked by Java code in Android apps via JNI (Java Native Interface). Our wrapper app_process program is a standalone native program, which needs to be compiled using NDK. For more detailed instructions about NDK, please refer to the instructional manual linked in the web page. To use NDK, we need to create two files, Application.mk and Android.mk, and place them in the same folder as your source code. The contents of these two files are described in the following:We run the following commands inside the source folder to compile our code. If the compilation succeeds, we can find the binary file in the ./libs/x86 folder. export NDK_PROJECT_PATH=. ndk-build NDK_APPLICATION_MK=./Application.mk Step 2. Write the update script and build OTA package. Just like the previous task, we need to write update-binary to tell the recovery OS what to do. Students need to write the shell script code in this task. Here are some guidelines: ● We need to copy our compiled binary code to the corresponding location inside Android. ● We need to rename the original app_process binary to something else, and then use our code as app process. The actual name of app_process can be either app_process32 or app_process64, depending on the architecture of the device. Our VM is a 64-bit device, so the name should be app_process64. Students should then repeat Steps 2 and 3 of the previous task, and describe their observations and explanation. Task 3: Implement SimpleSU for Getting Root Shell Now we know how to inject our code into the Android system and gain the root privilege, but we have not completely achieved our ultimate goal yet. An important reason for users to root their Android devices is to execute any command of their choice using the root privilege. When building the OTA package, the commands are already decided; if users want to run other commands after the programs in the OTA package is executed, they will not be able to do that, unless they can get a shell that runs with the root privilege. Such a shell is called root shell. We can launch the root shell using the methods from the previous tasks, but that is problematic: shell programs are interactive, meaning they will not terminate unless users type an exit command; this will stop the system booting process, so the OS will never be able to complete its booting sequence. The interesting question is how to run something non-interactive during the booting process that enables us to get an interactive root shell later on. If we were on a typical Linux system, we can easily solve the above problem by using the chmod command to turn on the Set-UID bit of any shell program (e.g. bash) that is owned by the root. Later on, when any user runs this shell program, the shell will run with the owner’s (i.e. root) privilege. Unfortunately, for security reasons, Android has removed the Set-UID mechanism from its underlying Linux OS since version 4.3 (API Level 18). The official document of security updates on Android 4.3 says the following:“No setuid/setgid programs. Added support for filesystem capabilities to Android system files and removed all setuid/setguid programs. This reduces root attack surface and the likelihood of potential security vulnerabilities.” Another approach is to start a root daemon during the booting process, and then use this daemon to help users get a root shell. This is the approach used by some of the popular rooting OTA packages, such as SuperSU developed by Chainfire. In this task, students will write such a daemon and use it to understand how it helps users to get a root shell. The main idea of this approach is quite simple. When users want to get a root shell, they run a client program, which sends a request to the root daemon. Upon receiving the request, the daemon starts a shell process, and “give” it to the client, i.e., allowing users to control the shell process. The tricky part is how to let the user control the shell process that is created by the daemon. For users to control the daemon-generated shell process, they need to be able to control the standard input and output devices of the shell process. Unfortunately, when the shell process is created, it inherits its standard input and output devices from its parent process, which is owned by root, so they are not controllable by the user’s client program. We can find a way to let the client program control these devices, or we can do it in a different way by giving the client program’s input and output devices to the shell process, so they also become the input/output devices for the shell process. This way, the user has a complete control of the shell process: whatever the user types in the input device of the client program will also be fed into the shell process; whatever the shell process prints to its output device will be showing to client program. Writing the code to implement the above idea is not easy, as we need to have two essential pieces of knowledge: (1) how to send the standard input/output devices (file descriptors) to another process, and (2) once a process receives the file descriptors, how it can use them as its input/output devices. We provide some background knowledge regarding these. Background File descriptors. Each process in Linux systems typically has three associated I/O devices: standard input device (STDIN), standard output device (STDOUT), and standard error device (STDERR). These devices are where the process gets its user input and prints out results and error messages. Processes access these devices through the standard POSIX application programming interface that uses file descriptors. Basically, I/O devices are treated just like they are files. The file descriptors for STDIN, STDOUT, and STDERR are 0, 1, and 2, respectively. In this task, we need to pass file descriptors from one process to another. File descriptors can be passed to another process either via inheritance or explicit sending. When a parent creates a child process using fork(), all the parent’s file descriptors are automatically inherited by the child process. Beyond this stage, if the parent wants to share a new file descriptor with its children, or if two unrelated processes want to share the same file descriptor, they have to explicitly send the file descriptor, which can be achieved using the Unix Domain Socket. In our code, our client program sends its file descriptors to the root shell process created by the daemon. File descriptors can be redirected. The system call dup2(int dest, int src) can redirect the src file descriptor to the dest one, so the file descriptor entry at index src actually points to the entry at dest. Therefore, whenever the process uses the src file descriptor, it actually uses the entry stored in the dest entry. For example, assume that we open a file, and get a file descriptor 5. If we call dup2(5, 1), we basically let the file descriptor 1 points to 5, causing anything printed out by printf() to be saved to the file that was just opened. This is because printf() by default prints out everything to the standard output device, which is represented by the file descriptor 1.Figure 3. File Descriptor Tables Figure 3 shows the file descriptor tables of two processes. The table of Process 0 is quite simple. It has three standard I/O FDs (indices 0, 1, 2), a file descriptor (index 3) for an opened file, and another file descriptor (index 4) for a socket. Table 1 is a little bit more complicated. It opened a device named /dev/null, and received a file descriptor from Table 0, and store the descriptor at index 4. Moreover, Process 1’s standard output and error are redirected to /dev/null, while its standard input is redirected to the one (index 4) received from Process 0. The consequence of such redirections is that Process 1 will take exactly the same input as Process 0, but all outputs are abandoned (/dev/null is a standard device that functions like a black hole: nothing written to it gets out). Creating new process. In Unix systems, we use the fork() system call to create a new process. The fork() call returns an integer: for the child process, the return value is 0, while for the parent process, the return value is the actual process id (which is non-zero) of the newly created child process. The child process inherits the parents data and execution status, as well as the file descriptors. A sample code is provided in the following: pid_t pid = fork(); if (pid == 0) { // This branch will only be executed by the child process. // Child process code is placed here … } else { // This branch will only be executed by the parent process. // Parent process code is placed here … }Figure 4. How one process (Client) gains the control of the input/output devices of another process Passing the File Descriptors. Figure 4 shows how to use the three standard I/O file descriptors to help the client gain the full control of the root shell created by the server. Initially, as shown in Figure 4(a), the client and server are running in different processes, while the client has a normal privilege and the server has the root privilege. Each of them has its own standard I/O FDs 0, 1, 2. In the figure, the client FDs are denoted as C_IN, C_OUT, and C_ERR, and the servers FDs are denoted as S_IN, S_OUT, and S_ERR. In Figure 4(b), we depict how the client and the server work together to help the client get the root privilege. 1. The client connects to the server using the Unix Domain Socket. 2. Upon receiving the request, the server forks a child process and runs a root shell. The child process inherits all the standard I/O FDs from the parent. 3. The client sends its FDs 0, 1, and 2 to the server’s child process using the Unix Domain Socket. These FDs will be saved in the table indices 4, 5, and 6, respectively. 4. The child process redirects its FDs 0, 1, 2 to the FDs received from the client, resulting in FDs 4, 5, and 6 being used the as the standard input, output, and error devices. Since these three devices are the same as those in the client, essentially, the client process and the server’s child process now share the same I/O devices (Figure 4(c)). Although the client process is still running with a normal user privilege, it has the full control of the server’s child process, which is running with the root privilege. Task 3 Questions Moreover, they need to show that their client process and the shell process do share the same standard input/output devices. In Unix-like systems, file descriptors of a process can be found in the /proc virtual file system, inside the /proc//fd/ folder, where is the process id. We can use the ps command to find out the id of a process. After completing the task, students need to look at the source code, and indicate where the following actions occur. Filename, function name, and line number need to be provided in the answer. ● Server launches the original app process binary ● Client sends its FDs ● Server forks to a child process ● Child process receives client’s FDs ● Child process redirects its standard I/O FDs ● Child process launches a root shell Part 2: Task4: Implement Location App In the previous tasks, we have rooted the Android system and successfully gotten the root shell. Although rooted system provides us with elevated privilege, it also puts the system into a dangerous situation. With a rooted device, the Android system security cannot be guaranteed, users or malicious programs can circumvent the system protections and get access to the private data of the users or other apps. For example, Rootnik is a malware example that checks for the existence of su binary and attempts to elevate its privilege to do malicious things. You will implement a small app that also checks for su binary and getting the private data from the device as well. Therefore, in this task, we will ask you to complete a small app that will show you how dangerous root a device will be. You will complete the app to leverage root access and get user location without permission. This application first checks if the user has rooted his device and if he rooted his device with a common method so that su could be run. Then, the app shows a map to the user. If the phone is rooted and superuser access has been granted, the app will steal the location information on the phone. If the phone is not rooted or su could not be run, the app will ask for location access permission like benign applications. The skeleton of this application can be found on canvas in lab 6 files. In the skeleton code, there are two main parts that you are required to complete: 1. Heuristic methods to check if device is rooted 2. Grant the application permission to get current location To work on your application, first of all, add the bottom permissions in AndroidManifest.xml so your device will know this app could be granted these two permissions some time when it runs. Second, in your application folder, check the below lines are included in the dependencies in app/build.gradle and the versions are correct. Since there are many ways to root an Android device and malicious attackers can come up with more sophisticated methods to avoid root detection, the methods existing currently to detect rooting are heuristic – they only check for common characteristics of a rooted device. In this app, you are asked to implement the checking for the Android Test-Keys and su binary to see if the phone is rooted and if your application can su as root. For this part, you will need to implement the three functions below: • checkTestKeys(): checking the BUILD tag for Android Test-Keys. By default, the Stock ROM has BUILD tag as release-keys while some custom Android ROM has Test-Keys. • checkSuBinary(): checking if superuser binary exist in some possible path in the system. Some type of superuser binary has to be installed when you want to authorize apps to run as root. • canSu(): By executing the su and id commands, it can be checked if the user has a UID of 0 (reserved for root on Linux). Next, you are required to get location access permission in two ways – regular way, asking the user to grant permission on devices that are not rooted; stealthy way, using super user access to grant itself permission on rooted device. There are three functions in MapsActivity.java that you need to implement for this part: • requestPermissionSuperUser(): since superuser is granted to the application and su could be run, you will need to implement this function to grant this application android.permission.ACCESS_FINE_LOCATION permission without user permission. (Bottom line behavior: the first time you run the application, it secretly grants the location access permission to the application; and later on when you restart the application, it can show the location mark of the device’s current location on the map.) • requestPermissionNormally(): since the phone is not rooted and su could not be used, you will have to check the current permission status and request the android.permission.ACCESS_FINE_LOCATION permission, if permission has not been granted, from the user like what regular application does. • onRequestPermissionsResult(int requestCode, @NonNull String[] permissions, @NonNull int[] grantResults): receiving the results for permission request and get current location. For this part of this project, you can develop the app locally on your computer using Eclipse or Android Studio or any IDE you want in the shared folder with the Ubuntu VM, or you can install the IDE on the Ubuntu VM and develop the app there. However, you will have to be able to generate an apk file that can be installed on the Android VM for testing. For Eclipse user, you can refer to this website for building unsigned apk file; for Android Studio user, you can refer to this one. To ship the apk file to the Android VM, you can run the command “adb install -r app-debug.apk”, it will be able to install the app for you. You can find more detailed guidance here. To test the app on the Android x86 VM, you need to use a mock location. Go to Settings -> Personal -> Location to turn on location, go to Mode, select Device Only to only use gps to determine location. Then, go to Settings -> About tablet, scroll down, tap Build Number multiple times until Developer options is unlocked. Go to Settings -> Developer options -> Debugging -> Select mock location app. Select MockLocation, then you can use MockLocation to give your VM a gps location. Run Google Maps to make sure that MockLocation is working. Note that there is chance that MockLocation does not work correctly. If it doesn’t, you can go to https://github.com/mcastillof/FakeTraveler, to download Fake Traveler app and build the .apk file locally. Then, run the command “adb install -r app-debug.apk” to install it on the Android VM. Set Fake Traveler as your mock location app. Go to the app to set location, click the three dots to set the number of mock times to be a large number and seconds between every mock to be 0, and then go back to apply location. Again, verify your current location is shown on Google Maps. You can then start to test your app. Note: if you get an error message: “Google Maps Android API: Authentication failure” with a blank screen but still get the toast notification and map marker when using the API, this indicates that the provided API key has exceeded its daily requesting quota. You can request an API key from google following the instruction on this website and use your own API key. Or you can wait until the next day and try again. To use your own API key, you can simply replace the provided one with your own API key in /debug/res/values/google_maps_api.xml. Another Note: if you don’t want the app prompt to you each time to ask for super user permission, you can go to Settings -> Superuser. At the upper right corner, tap the three dots for settings. You can set Automatic Response to Allow to always allow superuser permission request. You can even turn off the superuser notifications there. This is a super bad behavior in reality when you root your phone. You should never do this to your rooted devices. There is no limitation in what a malicious application can do when they get this permission from the root user. Therefore, be super cautious when you give superuser permission to unknown apps on your phone. For this task, you will need to submit a zip file of your source code with the .apk files generated for Android x86 VM. We will test the app on the Android VM. If you have specific instructions on how to run your app or any note on this app that you think doesn’t fit with the report, you can also include a README file. In your report, explain your implementations and include necessary screenshots and code snippets. Bonus There are two additional tasks you can do to get bonus points; you can complete either one or both: First, develop another malicious app that leverages root access to remove other apps, here you are asked to remove the MockLocation app and the Settings app. Briefly describe how you implement it in the report and the differences between removing a system app and a user-installed app. Remember to finish everything in the previous tasks before trying to touch the Settings app and make sure to take snapshots before you begin this task. Second, you can do some further investigation on the Android VM and root it in a second way. We provide two other common approaches in the beginning of the tutorial; you can try to research on them if you are interested. Describe in detail what you have done and what you have observed, including screenshots and code snippets. You can also include your thought process in the report too. You will get partial credit if you try but fail. To get you started, you can look for some CVEs of Android, for example about a kernel exploit that would elevate the privileges of the user to that of the root.Guidelines Android Booting Sequence and app_process Figure 5 shows a detailed booting process. In the figure, we assume that the bootloader choses to boot the Android OS, not the recovery OS. Phase I: The Kernel. After the bootloader switches the control to Android system, Android kernel will be loaded and starts initializing the system. Android kernel is in fact a Linux kernel, which handles some essential parts of the system, such as interruptions, memory protections, scheduling etc. Some Android- specific functionalities are added to the kernel, including logcat logger and wakelocks. Phase II: The Init Process. After the kernel is loaded, Init is created as the first user-space process. It is the starting point for all other processes, and it is running under the root privilege. Init initializes the virtual file system, detects hardware, then executes script file init.rc to configure the system. The script init.rc itself mainly focuses on mounting files inside virtual file system and initializes system daemons. However, it imports some other rc script files for various purposes, such as setting up environment variables, executing architecture specific commands, and launching zygote. Here are the files imported to init.rc: • init.environ.rc: Environment variables are set by init.environ.rc, which provides some important path-related environment variables. These paths are very important for launching further processes because many of them will try to access these paths using the corresponding environment variable names. In one of the lab tasks, we need to pass environment variables to the child process; now we see why that is needed.Figure 5. Detailed Booting Process ● init.${ro.hardware}.rc: Some commands or codes are architecture specific. The variable ${ro.hardware} is inherited from the Init process and passed to the init.rc script. On our Android-x86 VM, it will be “android_x86” and the script file init.android_x86.rc file will be invoked. Inside this file, init.sh is called. This init.sh file is the one used in In Task 1, where we inject the invocation of our code. ● init.${ro.zygote}.rc: This file starts a very important daemon called Zygote. The variable ${ro.zygote} is inherited from the Init binary. It can be zygote32 or zygote64, for 32-bit and 64-bit architecture, respectively; it can also be zygote32_64 or zygote64_32 for hybrid modes (mainMode secondaryMode). In our Android-x86 VM, it is init.zygote32.rc. All these rc script files are stored in an image file, named ramdisk.img on our Android-x86 VM; on real devices, these script files are inside boot.img, which contains ramdisk.img and the kernel. The ramdisk.img file will be extracted into the memory while booting up. Making modifications directly on an image file is not very easy. That is the main reason why we only change the init.sh file in our first task, because the init.sh file is inside the /system folder, not inside those image files. Phase III: The Zygote Process. In the init.${ro.zygote}.rc file, a special daemon is launched by the Init process via the “service zygote /system/bin/app process …” command (options are omitted). The command starts a daemon called zygote, which executes the app_process binary. Zygote is the starting point of the Android runtime. It starts the runtime environment of Dalvik or ART, which are virtual machines that run Java programs. In Android, system servers and most applications are written in Java, so Zygote is an essential daemon, and it runs with the root privilege. That makes app_process another place to insert our rooting code. The app_process file is not a real binary file; it is a symbolic link, pointing to either app_process32 or app_process64, depending on the architecture of the system. Therefore, we just need to change the symbolic link, and let it point to our code. In our code, we will have two processes, one running our rooting code, and the other running the original app_process code. This approach is commonly used by many existing rooting OTA packages. How to unlock the boot loader on a real device As what is shown in Figure 5, when the power button is pressed, the device firsts goes to a fixed location in its ROM, and run instructions from there. These instructions will then go to a pre-defined location on the disk or flash drive to load the bootloader, and pass the control to it. Bootloader then loads the operating system, and eventually gives the control to the loaded OS. Most of the Android devices come with two operating systems, an Android OS and a recovery OS. By default, the bootloader will choose the Android OS to boot; however, if some special key combination is pressed during the booting, the bootloader will boot the recover OS instead. On Nexus devices, this is achieved by pressing the “Volume Down” and “Power” buttons together. Bootloader usually have another functionality that is often disabled by default. This functionality allows users to replace (often called flash) the OS images on any of the partitions, so users can install a different recovery OS or Android OS. Most manufacturers do not want users to make such kind of modifications to their devices, so before shipping devices to customers, they disable the functionality, and hence we say that “the bootloader is locked”. With a locked bootloader, any attempt to flash the installed OS will be denied by the bootloader. The following command tries to flash the recovery OS with a locked bootloader; as we can see, we get an error message: # fastboot flash recovery CustomRecoveryOS.img sending ’recovery’ (11600 KB) … OKAY [ 0.483s] writing ’recovery’ … FAILED (remote: not supported in locked device) finished. total time: 0.585s Some vendors choose to permanently lock the bootloader; in this case, it will be very hard to flash the OSes on the devices. However, many vendors choose not to do so, and instead, they provide instructions to unlock the bootloader, so users who really want to flash their devices can still do that. We will show how to unlock the bootloader. For the demonstration purpose we are using a Nexus device. To unlock it, first we need to load bootloader of the Nexus device by passing the “adb reboot bootloader” command or by interrupting the normal boot process using the “volume down” and “power” button combination. Figure 6(a) shows the bootloader screen of a Nexus 5 device, which indicates that the bootloader is locked. Bootloader of Nexus devices can be unlocked by using the “fastboot oem unlock” command. Be very careful while unlocking the bootloader because it will void the manufacturer’s warranty and completely wipe out personal data on the device. We advise you to backup your personal data before unlocking the bootloader. You can also backup your installed apps and app data by using the “adb backup -apk -all -f backup.ab” command, which creates a file called backup.ab. After unlocking the bootloader, you can restore the data by running “adb restore backup.ab”. Figure 6(b) shows the confirmation screen, and Figure 6(c) shows that the bootloader is now unlocked.Figure 6. Unlock BootloaderHow to replace the existing recovery OS on a real device On real devices, to remove the restrictions imposed by the stock recovery OS, such as signature verification, we have to replace it with a custom recovery OS that does not impose such restrictions. A number of custom recovery OSes are available on the market. TWRP and ClockworkMod are two of the best choices. We are going to use TWRP in our description. To flash custom recovery we need to unlock the bootloader of the device. We assume that you have already unlocked the bootloader. We can boot the custom Recovery OS by using the “fastboot boot CustomRecoveryOS.img” command, or we can permanently replace the device’s stock recovery OS with TWRP. The following command flashing the custom recovery OS onto the recovery partition: # fastboot flash recovery CustomRecoveryOS.img sending ’recovery’ (11600 KB) … OKAY [ 0.483s] writing ’recovery’ … OKAY [ 0.948s] finished. total time: 1.435s After that, we can boot into the recovery OS by pressing the “volume down” and “power” button combination during the boot-up process. Figure 7(a) shows how to boot into the recovery OS, and Figure 7(b) shows the user interface of the TWRP recovery OS. As you can see, it has several useful features.Figure 7. Custom Recovery OSSubmission Your submission should include two files. First, you need to submit a detailed lab report to describe what you have done and what you have observed, including screenshots and code snippets (if needed) for Task 1-4 and Bonus. You also need to provide explanation to the observations that are interesting or surprising. You are encouraged to pursue further investigation, beyond what is required by the lab description. Second, you also need to submit the zip file for your source code for Task 4 and Bonus. The zip file should include the .apk file for your applications and another zip file containing the source code for the entire Task 4 and Bonus part and a README (if needed).
Exploring Modeling & Attacking PE Models via MLSploit Disclosure Goals The purpose of this assignment is to gain experience with training machine learning (ML) and deep learning (DL) models classifying Windows portable executable (PE) malware into families. Specifically, the models will be given two different datasets: benign PE files and malicious PE files from multiple families. After training, you will attack those models using an evasion attack called the Mimicry Attack [1]. Finally, you will be tasked with improving the models which were attacked and write a report about your experiences and observations. The malware binary we provide you (and the malware produced by MLSploit) is real malware. Do not under any circumstances execute these malware EVER. It is a compiled form of the rbot malware family and antivirus companies are well-aware of their existence (https://github.com/ytisf/theZoo). We have not applied any static obfuscation to them so they should be easily detectable by AV companies. You are to use these binaries responsibly by only reading their byte contents (e.g., using tools like https://github.com/erocarrera/pefile). Requirements To perform this lab, you will need a basic understanding of what computer malware is, along with some knowledge of how ML models are trained to detect and classify them. You will need to know how to program and how to train ML models using libraries (e.g., http://scikit-learn.org/stable/). Finally, you should be familiar with how the PE file format is structured (https://docs.microsoft.com/en-us/windows/win32/debug/pe-format). Overview: Grading is out of 100 points. [10 points] Task 1: Training DL Models • Train LSTM, CNN, and RNN models on API call sequences. [10 points] Task 2: Attacking DL Models • Attack models via mimicry attack. [20 points] Task 3: Detecting Attack • Train model based on static features to detect the attack sample. [10 points] Task 4: Training classic ML Models • Train models based on additional features (API existence, frequency, and arguments). [10 points] Task 5: Attack Transfer to ML Models • Evaluate how the attack sample evades detection from these models. [10 points] Bonus Task • Use machine learning to evade malware detection models. You will use two open-source toolsets: one which detects malware using static features and one which trains a reinforcement learning model to craft malware samples which evade the detection model. [40 points] Written Report • You will be graded based on how well this report is written. Times New Roman 12-pt font. Include diagrams of your work and citations to back up your claims and assumptions. Can include screenshots of your experience with MLSploit, but add these to an Appendix at the end of the report (you will not be graded based upon them). Setup You will be using MLSploit for a majority of this assignment. You will use it to train and attack machine learning and deep learning models of PE malware. a. https://oit.gatech.edu/services/end-point-computing/virtual-private-network-vpn b. https://faq.oit.gatech.edu/content/how-do-i-get-started-campus-vpn c. https://vpn.gatech.edu/https/mlsploit.org/ • Create an account on https://mlsploit.org a. Use a strong password. • Read the “PE Module Tutorial” and “MalwareLab Module Tutorial” attached with this assignment. • For your own information, the functions of the PE module (with exception to the PE transformer – which performs binary rewriting to statically modify PE binaries in order to implement attacks) are open sourced here: https://github.com/evandowning/mlsploit-pe • Finally, only a certain number of jobs will be allowed to run at once on our internal servers. So if you see that your job is “PENDING” don’t worry. It should change to “RUNNING” within an hour or so depending on the jobs other students are running. Submitting Answers Compress the deliverables for each task into a .tar.gz file called [GTUsername]_cs6264_lab07.tar.gz with the following directory layout: • task1/ • pe.model.zip • prediction.zip • *.log.txt files • task2/ • attack-exe.zip: the attack samples generated from MLSploit to evade your models • attack-feature.zip • attack-prediction.zip • attack.cfg.zip: Configuration file from MLSploit • *.log.txt files Submitting Answers • task3.a/ • detection1.py: Source code (preferably in Python) that will train a new model that will detect the attack from the previous task • detection2.py • detection3.py • (others here if you wish) • task3.b/ • model1.zip • model2.zip • model3.zip • (others here if you wish) • task4/ • pe.model.zip • prediction.zip • *.log.txt files Submitting Answers • task5/ • prediction.zip • *.log.txt files • bonus/ • model.zip • *.log.txt files • report.pdf: • This report should contain screenshots of your findings and explanations for why the certain screenshot happened. For example, if your screenshot is comparing the results of how well different models detected the attack in part 2, then an explanation for why the results differed should be included. Introduction One of the goals of a security company is to detect malware over time: old known malware (e.g., Zeus), new malware variants (e.g., Gameover Zeus, Spyeye, Carberp), and new malware (e.g., Petya). Once a new malware family (or variant) has been discovered, the company needs to update their end-host solution to be able to identify it. The purpose of this lab is to expose you to this scenario: to classify malware into families. The goal of classifying malware is to understand what type of malware you have identified. This is subtly different from malware detection (the goal of which is to determine if something is malware or not). The benefit of classifying malware is to use what you have seen in the past to help with your task. For example, if your goal is to automate cleaning a victim’s machine after an infection, it could be useful to know what family of malware infected it (i.e, family A is known to affect files and registers x, y, and z, so those need to be removed or reset). If your goal is to reverse engineer a malware sample (e.g., to study it further), it could be useful to know what family it belongs to in order to identify specific regions you know exist (e.g., family A is known to have a ransomware encryption routine and an IRC C&C routine, thus we should look for API calls which are indicative of these activities).There are too many new samples and variants generated every day to simply hand-label each malware binary. Luckily, machine learning (ML) can be used to classify malware samples without having to do so. In general, machine learning works as is illustrated in Figure 1. First, the analyst collects many malware samples with their associated malware family labels. Second, they identify and extract features for discriminating between each malware family (e.g., API call sequences, static features, network features, etc.). Finally, they train a ML model to distinguish these features for each family. To evaluate how well the model has learned, they save a portion of their dataset (not used for training the model) and test how accurate the model is at predicting the labels of each unseen sample.Figure 1: General workflow of training and using a malware classifier However, this process can be tedious and requires some knowledge in order to (1) identify and extract these features and (2) implement, train, and evaluate the ML models. Thus, we developed MLSploit. MLSploit is a framework developed by Georgia Tech PhD students with oversight from Georgia Tech Professors and Intel research scientists (http://istc-arsa.iisp.gatech.edu/). Its goal is to assist its users to train and test various machine learning solutions (e.g., image classification, object recognition, malware detection & classification) against various attacks without requiring a significant amount of experience in machine learning and information security. The tool decreases the barrier of entry normally required to run these types of experiments and evaluations. You will notice that this tool is relatively easy to use: it essentially does the work for you in terms of implementation. The only challenges you face in this project are (1) deciding what parameters to use for each ML model (in order to produce an accurate model) and (2) having an imagination to explain the results you see and deciding what features you’ll choose to accomplish Task 3.Task 1: Training DL Models Your first task will be to train 3 deep learning models using API call sequences. As described in the tutorial, select “New Pipeline” and name it something like “DL Training”. Then click-and-drag training ensemble models from the PE module in the left-hand column. Train an LSTM, RNN, and CNN model on sequences on pe.train.txt (provided to you). Begin with a sequence window size of 32, but try increasing and decreasing it to achieve better accuracies. Note that shorter sequences will take much longer to train. Also attach an ensemble evaluation and use pe.eval.txt. Download the resulting model files (contained in a single zip file), predictions (also in a zip file), and log files. Task 1: Training DL Models • Behind the scenes: We have implemented using these three deep learning models using Keras (https://keras.io/). The sequences model takes as input, the window size. This window size is the length of each subsequence that the model gets trained on. The model can perform malware detection (i.e., binary_classification) or malware classification (i.e., multi_classification). After running this module, you will get a trained model along with the predictions that it made for each sample. • Time duration: This should take about an hour or two to finish running (depending on the servers’ usage), so start this ASAP. • MLSploit Input Files: pe.train.txt, pe.eval.txt MLSploit Output Files: pe.model.zip, prediction.zip, and log.txt files. • MLSploit Hint: Set pipeline to train and evaluate all three models simultaneously (i.e., select “true” for all three sequence_xxx) while you find the ideal window size. • Hint: you can find the accuracies in the log.txt file, the prediction.zip file gives you the classification results of the samples of each model. • Deliverable: Output files produced by MLSploit website. Task 2: Attacking DL Models Perform the mimicry attack [1] using MLSploit similar to how it is described in the tutorial. Create a new pipeline and name it something like “Mimicry Attack”. Upload the file “pe.benign.txt” given to you as well as a zipped file of the models you trained in Task 1. Also, upload the file “pe.target.txt” given to you. It contains the filename of the malware you will be morphing to attack the models. The mimicry attack will discover a sequence of system calls which will precisely mimic the system calls produced by a benign application. Thus, any classifier will conceptually misclassify it as benign software (given the same datasets). This task will produce a series of API calls which will evade the models along with a configuration file. Give these files to the PE transformer, which will generate whole new samples. This module will produce a runnable executable which will exhibit the behaviors the attack module defined. The parameter for the PE Transformation function asks for a “hash value”, but it’s really the file name of the binary. Finally, give the resulting malware to the models and evaluate them to demonstrate that the attack worked. For the PE Transformer’s hash parameter use “rbot-original.exe”. For generations, use 10, it will produce 10 malicious executables for mimicry attack. Note that these attack predictions are made off of what the malware is *expected* to execute. Later, in Task 5, we’ll actually execute these malware samples and observe what is *actually* executed (verifying that our malware will dynamically evade these models). Task 2: Attacking DL Models • Behind the scenes: This code creates new sections in the Windows PE file that call API calls with various arguments. It then searches for targeted calls within the binary (e.g., whenever it calls WriteFile()) and inserts jump instructions to this new section (thus inserting a new API call after, say, WriteFile()). This process of modifying a binary is called binary rewriting. After running this module, you will receive multiple binaries (10) which have been rewritten to insert API calls during the malware’s execution. Thus its goal is to evade dynamic API-based malware detection/classification models. • Time duration: This should take around 10 minutes to finish running (depending on the servers’ usage). • MLSploit Input Files: pe.benign.txt, pe.target.txt, pe.model.zip [From task 1 training pipeline’s outputted files. • MLSploit Output Files: attack-feature.zip, attack-prediction.zip, attack.cfg.zip, attack.exe.zip, log.txt files. • MLSploit Hint: The pipeline described in the tutorial performs all of the necessary steps as described. The attack-exe.zip has the password “infected”. Do not execute these binaries under any circumstances. • Deliverable: Output files produced by MLSploit website.For this task, you will not be using MLSploit. You will be writing a program to train a ML model yourself using features you choose. Since MLSploit is open-sourced (and there are numerous tutorials on scikit-learn), it should be painless for you to train a ML model. The only real challenge is picking the features you’ll train it on. We have provided you with a code template. This task is left intentionally bare with few guidelines – use your imagination and think critically about the features you will choose. Now is the time to be creative! Train a new model on static features (i.e., features you can get directly from the samples without executing it) to detect the attack instance. Since we trained models on dynamic features (i.e., API call sequences), we need to find some other feature not based on API call (since our Mimicry attack ran on those features). Use the provided static features file for all samples (benign and malicious) to come up with new features (combinations of features from the static features file) to more reliably detect the attack (as you’ll see some of the benign samples get detected as anomalous as well). You need to unzip the attack.exe.zip (which contains 10 mimicry attacks) file and statically examine the differences between it and malware-original.exe to discover some interesting artifact (or side-effect) of the attack (e.g., using pefile, readelf, objdump etc.). Compare your assumptions to the static features of the other malicious and benign files to determine if your hypothesis is valid. The features can be found in the JSON file attached with this assignment. These static features were extracted with EMBER (referenced below). Notice that all features for all binaries pe.train.txt are provided. You now need to extract them from attack-x.exe using EMBER. To do this, review ember’s code on how they extract their features (https://github.com/endgameinc/ember/blob/master/scripts/train_ember.py#L25, https://github.com/endgameinc/ember/blob/master/ember/__init__.py). Important distinction: The goal of this task is to detect evasive malware (i.e. morphed malware via unnatural artifacts introduced into the binary). Its goal is not to detect the malware itself. Your results should show that the benign software (along with the original malware sample) are nominal and the attack malware samples as anomalous. Hint 1: For example, because of the way the PE transformer adds API calls to be executed dynamically, more https://github.com/endgameinc/ember. You can use this script to help you extract features: https://github.com/evandowning/ember/blob/mlsploit/scripts/extract.py. Hint 2: We recommend you use Python to create your new models because it has support for easy-to-use ML libraries (http://scikit-learn.org/stable/). You can also look at the open-sourced modeling code that the PE module uses to get an idea of how to extract features from malware and train ML models on them: https://github.com/evandowning/mlsploit-pe. Deliverable: Source code to train models to detect attack (given entire dataset). (We have provided you a template for you to get started, it is up to you to choose to use it or not.) Use at least three different features from the static features file (separately or in combination as your choice) on three different models. Explain in your report why you chose the features and models you did. For example, provide a graph comparing the feature you chose for detecting the attack sample with the unmodified dataset (origin benign/malicious dataset). Is the model you chose good for the features you extracted (e.g., low versus high dimensional features)? Also discuss if these new features scale for future unknown samples and why? Discuss how an attacker can also evade your new features? Provide citations to academic or industry papers where appropriate.Task 4: Training classical ML Models Train at least 3 more ML models on other features (API call existence, frequency, and arguments) using MLSploit. For each feature you can train any one of a number of classical ML models: Random Forest, Neural Network, Naive Bayes, k-Nearest Neighbors, or Stochastic Gradient Descent. Read scikit-learn’s documentation to learn more about each model. Two parameters can be manipulated: the number of trees in the random forest, and the value of k for k-Nearest Neighbors. Task 4: Training classical ML Models • Behind the scenes: Similar to Task 1, this module implements classical ML algorithms from scikit-learn (http://scikit-learn.org/stable/). In Task 1, you trained DL models on API call sequences. This module trains other API-related features: existence (whether or not an API call was executed), frequency (the number of times an API call was executed), and arguments (the arguments passed to each API call). • Time duration: In the worst case, if all model architectures are chosen for each feature (for a total of 15 trained models), expect it will take at least 30 minutes to finish (depending on MLSploit’s server’s traffic). • MLSploit Input Files: pe.train.txt, pe.eval.txt MLSploit Output Files: pe.model.zip, prediction.zip, and log.txt files. • Deliverable: Trained models produced by MLSploit website. Task 5: Attack Transfer to ML Models • Evaluate whether or not the attack sample evades the ML models as well using MLSploit. • To do this, we must first execute the malware in a controlled, responsible environment. We use an in-house analysis framework called MalwareLab. Copy the 10 attack executables (from attack.exe.zip of Task 2) into a new single folder “attack-exe” and compress it via zip with no password. Upload that zipped folder to mlsploit.org. Then, run the “Submit” function via the MalwareLab pipeline (as demonstrated in its tutorial). Task 5: Attack Transfer to ML Models • Behind the scenes: This module executes the evasive malware samples you generated back in Task 2 in a safe and controlled environment. • MLSploit Input Files: attack-exe.zip MLSploit Output Files: log.txt files Task 5: Attack Transfer to ML Models Once the samples are finished executing, we can evaluate our trained classical models (from Task 4) on the dynamic traces. To do this, we can create a new pipeline with just “Ensemble-Evaluate”. The MalwareLab module will output logs denoting the SHA-256 value of each executable submitted. Create a file “attack.eval.txt” of these hash values (similar to how pe.train.txt and pe.eval.txt are formatted). I.e., each line is formatted as “hash_value TAB rbot” Task 5: Attack Transfer to ML Models • Behind the scenes: This module is something you’ve already run before. It extracts features from the malware you just executed and runs them through the models you just trained. This will show whether or not the samples which evaded the DL models in Task 1 also evade the ML models you trained in Task 4. • MLSploit Input Files: attack.eval.txt pe.model.zip [the one that was outputted from tasks 1 & 4] • MLSploit Output Files: prediction.zip and log.txt files. • Deliverable: Results on how DL & ML models classify the attack samples from Task 2 above. Explain in your report why the models were or weren’t successful at classifying the malware. How do these new features compare to the ones you studied in Task 1?The goal of this task is to gain experience using reinforcement learning (a type of machine learning technique) to generate malware samples which evade a pretrained model. To train this new model, you will be using Ember, a non-peer reviewed (i.e., self-published) paper which extracted static features from 50k PE malware samples and 50k benign PE samples and trained a classifier to determine if the sample is benign or malicious [2]. They achieved decent accuracy with their features (which are based on prior works which extract static features from malware for malware detection). First, please read this paper [2] to fully understand their methodology. Next, run this on MLSploit by creating a new pipeline (using PE Module) with (1) Ensemble-Train (enabling Ember) and (2) Ensemble-Evaluate (enabling Ember). • Behind the scenes: The code MLSploit uses can be found here: Ember (https://github.com/evandowning/ember/tree/mlsploit). MLSploit will use this code (specifically train_ember.py and test_ember.py) to train the Ember model using the authors’ dataset. The dataset of 100k samples used in the Ember paper already exists on MalwareLab’s servers. • Time duration: This should take about 30 minutes to finish. MLSploit Input File: pe.train.txt and pe.eval.txt • MLSploit Output Files: pe.model.zip and log.txt files. First, please read this paper [3] to fully understand their methodology. • Behind the scenes: The code MLSploit uses can be found here: Gymmalware (https://github.com/evandowning/gym-malware/tree/mlsploit). Logic for what features they modify and how can be found here: https://github.com/evandowning/gymmalware/blob/mlsploit/gym_malware/envs/controls/manipulate2.py#L367. • Time duration: This should take about 30 minutes to finish. MLSploit Input File: pe.model.zip • MLSploit Output Files: ember-attack.zip and log.txt files. Deliverable: Please add your answers to the questions to the written report document above. After training and generating malware samples which evade the static model, answer the following questions and put them into your report (above): Questions: (1) What things were changed about the binaries to make them successfully evasive? (see standard output) (2) How effective is this method compared to mimicry attack? I.e., number of successfully evasive malware samples produced by both methods, time it takes to produce evasive samples, etc. (3) Similar to how the mimicry attack was implemented to produce new binaries, how does this method compare? How can a defender identify likely suspicious binaries? (4) Submit the evasive samples to VirusTotal. What does it classify them as? What does this tell you about AV company static-based malware detection solutions? Attach the VirusTotal reports to your solutions folder.Written Report Please compile a document describing your experience and your decision processes with training DL models and choosing features to detect the attack sample, as well as the results of the attack samples on the classical ML models. Include diagrams of your work and citations to back up your claims and assumptions. Can include screenshots of your experience with MLSploit, but add these to an Appendix at the end of the report (you will not be graded based upon them). Quality is always valued higher than quantity. There is no page limit nor minimum page requirement, but do not write more pages than is needed to communicate your ideas and answers to questions effectively. References [Online]. Available: http://dl.acm.org/citation.cfm?id=586145. [2] H. S. Anderson and P. Roth, “Ember: an open dataset for training static PE malware machine learning models,” arXiv preprint arXiv:1804.04637, 2018. [Online]. Available: https://arxiv.org/abs/1804.04637. [3] H. S. Anderson, A. Kharkar, B. Filar, D. Evans, and P. Roth, “Learning to evade static pe machine learning malware models via reinforcement learning,” arXiv preprint arXiv:1801.08917, 2018, [Online]. Available: https://arxiv.org/abs/1801.08917.
CS8803 – O11 Overview ● Goal ○ Analyze real world malware samples and reveal their hidden/true behaviours which normally you don’t see without triggering properly. ● Learning Objectives: ○ Reverse Engineering ■ Manual Binary Reversing through Disassemblers (e.g. Ghidra, Radare2, IDA Pro) ○ Static Analysis ■ Programmatic binary analysis (e.g. data-flow analysis, VSA analysis.) ○ Symbolic Analysis ■ Performing symbolic execution to figure out the whole input or partial of the input ○ Dynamic Trace Analysis (User-level Activity Traces) ■ API Trace (e.g. File, Process, Registry, Network etc. related API trace) ■ BasicBlock Trace (Address of the basic blocks executed while malware is running) ○ Dynamic Binary Instrumentation ■ Manipulating concrete execution using DBI tools (e.g. DynamoRIO) Please don’t run the malware on your own computer! We are not responsible if you do. Only execute it inside the Windows VM we are provided. These are real world malware samples. Task Description ● You have 3 real world malware to analyze. Your boss wants you to analyze them and write a report within two weeks, and your colleagues are waiting for your results to adjust defense mechanisms to IDS. ● As a malware analyst, to build a strong defense mechanism, your job is to try to reveal all of the behaviours as much as you can. However, most of malware (especially C2-based malware) are only revealed hidden behaviors when the proper inputs (e.g. commands from C2-server) are provided. ● Now, you are going to analyze the three real malware samples with your best weapons (the tools we provide). You are going to perform: ○ Static analysis and reverse engineering on them to find where the triggering logic (e.g. CMD dispatching logic) is located. ○ Symbolic execution to figure out the commands that will trigger hidden behaviors ○ Dynamic binary instrumentation to manipulate execution paths to trigger the hidden behaviors and to collect traces that are corresponding to the behaviors. Agenda ● Part 1: Analyze malware1.exe(mydoom1.exe) malware which is similar to previously analyzed malware. Trigger the malicious behaviours and observe the effects on the OS. (60 pts) ○ Skills : ■ Reverse Engineering, ■ Static Analysis ■ Symbolic Analysis ■ Limited Dynamic Analysis Agenda ● Part 2: Analyze malware2.exe(win33.exe) malware which is new to your company. Trigger the malicious behaviours and observe the effects on the OS. (30 pts) ○ Skills ■ Reverse Engineering, ■ Static Analysis, ■ Symbolic Analysis ■ Extensive Dynamic Trace Analysis ■ Dynamic Binary Instrumentation and Execution Modification Agenda ● Part 3: Analyze one newly discovered complex malware(unknown.exe) and figuring the CMD Dispatching Logic without having prior investigation. ○ Static Analysis (analyze 10 functions) (10 pts) ■ Reverse Engineering ● Bonus: Perform further sophisticated analysis and reveal the malware behaviour: ○ Detecting whole or part of the input (5 pts) ■ Reverse Engineering ■ Symbolic Analysis ○ Triggering the malicious behaviour and observe the OS interaction (5 pts) ■ Dynamic Binary Instrumentation ■ Dynamic Trace Analysis Note: Even if you can’t figure out any part of the malware, you can still include any meaningful efforts of revealing the behavior of the malware. We will assign credit accordingly. High-level Workflow ● Your company has a static analysis tool leveraging Ghidra (developed by the NSA) to detect the important logic such as CMD Dispatching logic which is responsible for determining which malicious behaviour to perform.However, this tool only produces some candidate functions, ● Your first task is to perform Reverse Engineering using Ghidra to detect the real CMD Dispatching logic. To do so, you need to analyze each candidate function until you find the actual CMD Dispatching logic. ● Second, after discovering the CMD Logic, you are required to construct symbolic execution scripts using angr which will output whole or partial inputs for each behaviour. ● Third, you have to properly trigger the malicious behaviours and execute them during concrete execution. The Dynamic Execution Trace will show the malicious activities performed by the malware samples. Available Artifacts (Free Lunch?) ● Last week, One of your colleagues analyzed a sample malware (sample.exe) last week and created a report. ● That malware looks very similar to the malware malware1.exe which is one of the three malware samples you will analyze for the next two weeks. ● That report is quite informative. ● Fortunately, the report is open to your access and you can take advantage of your colleague’s report and findings. ● Having said that, the report lacks of how to actually execute the behaviour. Your colleague was failed to show the effects on OS such as file system or network operation. Hence, the colleague was failed to prove the nature of the malware sample. Tutorial (your coworker’s report) Let’s scrutinize the report for sample.exe.Before you begin ● Set up a Virtual Machine for Malware analysis ○ Please install/update to the latest version of VirtualBox ■ https://www.virtualbox.org/wiki/Downloads ● Download the VM image ○ Download the project VM from the following link ■ https://drive.google.com/open? id=1a_1U2UQKQ0268NApFnFHfV2HETZZEu4Z ■ We recommend you to download the VM via curl or wget due to the size of the VM. Helpful link: https://stackoverflow.com/questions/25010369/wget-curllarge-file-from-google-drive ■ Note: students have the freedom to adjust VM specs after import Before you begin ● Open VirtualBox ○ Go to File -> Import Appliance. ○ Select the ova file and import it ● VM user credentials ○ Ubuntu VM password: 123456 ○ Windows 7 VM Password: 123456 Project Structure ● VM Structure ○ A Windows 7 VM inside Ubuntu 18.04 VM ■ Windows 7 VM for dynamic analysis ● Target Malware can be executed in Windows 7 VM ■ Ubuntu VM for static analysis ● A container to block malware from going out Project Structure ● In the Windows Virtual Machine(VM) ○ C:codeconcrete_executor ■ $python run.py ##will run the tracer program ■ tracer ## tracer folder(where you need to write some code) ○ C:codedynamorio ■ Dynamorio source code and already built client ○ \VBOXSVRVM_Share ■ Shared folder with host VM● Go to Ghidra folder and Run Ghidra ■ $ ./ghidraRun ● Use “import file” to import binary into Ghidra project● Double click on the binary file that appears under the project to open Ghidra GUI and analyze the binary. Then close the GUI and Ghidra completely to save the result into Ghidra database ● There will be an warming about PDBs, which won’t affect your analysis● In order to have some basic knowledge of the malware, you usually start by analyzing it using a disassembler like Ghidra, Radare2, BinaryNinja or IDA pro, while Ghidra is free and open source (NICE). ● Meanwhile, lucky enough that your coworker sent you a static analysis tool based on Ghidra, which detects the possible dispatching logics. Then all you need to do is to iterate over the candidates and determine the real dispatching logic. ● To use the provided Ghidra Script ● Close Ghidra project GUI ● In /ghidra_9.1.1_public folder, go to /support, you will find a file called: analyze.sh ● This wrapper script runs the ListFunctionAsCodeBlock.java script with a headless analyzer and pipes the output into output.txt ● Usage: $ ./analyze.sh {malware.exe} ■ (just the file name is enough, no need to append PATH) ● To be able to run the script, you MUST first analyze the malware in Ghidra and save the result into Ghidra database ● Note: Ghidra must be closed completely, in order to run the headless script● The script will output top 50 longest chain of basic blocks that uses certain variable in the end. ● To view these chains, run $tail -53 output.txt● Reopen the Ghidra GUI ● Inside the Symbol Tree, you can find a folder called Functions. ● The first function in your coworker’s Ghidra script’s output is FUN_00804d32, so you decide to double click it● The Decompile window on the right gives you the decompiled version of the function that you just double clicked. And you could check the logic of this function in a more readable form● You notice that there is the dispatching logic between line 25 to line 31 (lucky!)● You want to see a clearer form of the control flow graph, so you click on the Display function graph button and the CFG pops up.● After knowing some possible information about the dispatching logic, you want to construct symbolic execution script using angr to output whole or partial inputs for each behaviour. ● Note: Your script should run with python3 ● In essence, You want to find some keywords that will trigger the malware’s activities ● Let’s take another look at our CFG for the Dispatching Logic ● This chain of basic blocks(0x804d6a, 0x804da2, 0x804db6, 0x804dca) is responsible for the dispatching logic. ● The chain uses a function to determine the triggering logic — strstr. ● All the strstr functions takes the EAX register as a pointer to the first parameter and some constant as a second parameter. ● Since all the second parameters are constants, we should focus on the first argument which is pointed by EAX. ● If you go backward from the chain of basic block, you can see EAX value is determined in basic block 0x804d6a. ● The call instruction to lstrcpyA at 0x804d79 will copy the buffer pointed by ESI to the address held by EAX — EAX being the first argument and ESI being the second argument for lstrcpyA. ● However, the source of the copy operation is also another register. ● We need to perform further static backward slicing to detect the original source of the command. ● While going backward in the CFG, you will see the last update to the ESI register is performed at 0x804d44 with mov ESI, [EBP + 8] . ● In x86 calling conventions (e.g. cdecl, stdcall), EBP+8 points the the first argument passed to the function. ● Hence, we now know the symbolic analysis needs to solve the value of the first parameter (EBP + 8) passed to the function 00x804d32. ● Now, we know where the variable that is passed to the malware resides, and can find keywords that reach the target function in the malware! ● Fortunately, your colleague also had a symbolic execution script for sample.exe (NOTE: sample.exe is similar to malware1.exe!). ● The report also shows the start and end addresses for the symbolic execution — start:0x804d32 end:0x804dde ● From your terminal go to ~/Desktop/symbolic_execution/ folder and run ○ python sample_inputs.py –start 0x804d32 –end 0x804dde ● It will print out one of the concretized inputs that malware requires to expand its malicious behaviour.Tutorial – Symbolic Execution ● However, there is no free lunch. ● Using the same start and end addresses, you need to find all the commands. ○ Let’s analyze the code snippet below. When performing symbolic execution, symbolic execution engine can find the path condition for ddos_attack as message[0] = 101 ○ Once we already explored ddos_attack, you need to explore other branches now. ○ To explore other branches, you need to add constraint such as message[0] != 101, hence the path conditions for ddos_attack becomes infeasible. ○ Once, you are done with send_spam, keep adding the condition inverses to explore other behaviours. ○ Copy sample_inputs.py as malware1_inputs.py, and modify the code. ○ Add a constraint for each found input such as ■ parameter[0] != found_input[0] ○ Extra hint: you should use ○ an inverse_constraints array to output all strings at one ○ run Tutorial – Symbolic Execution Extra Help for Angr: Angr’s Solver Engine: Claripy && How to add constraints https://docs.angr.io/advanced-topics/claripy https://docs.angr.io/core-concepts/solver Tutorial – Dynamic Analysis ● Now, it is time to practice Dynamic Binary Instrumentation and Dynamic Trace Analysis. ● For this purpose, we already have a DynamoRIO client to capture the API traces and Basic Block addresses captured during concrete execution. ● Your colleague’s report also shows how to use and manipulate the values of the function arguments. ● The report shows the execution successfully reaches to the 0x804dde. ● However, your colleague again failed to capture and prove what malware is doing.● We need a secure experiment environment to execute the malware. ● Why? ○ Insecure analysis environment could damage your system ○Encrypting your file during a ransomware analysis ○Infecting machines in your corporate network during a worm analysis ○Creating a tons of infected bot client in your network during a bot/trojan analysis ● The solution: ○ Contain malware in a virtual environment ■Virtual Machine ■Virtual Network ● Conservative rules(allow network traffic only if it is secure) ● Run $sudo iptables -A OUTPUT -o enp0s3 -j DROP: ○ DROP all — anywhere anywhere ● You can check if the rule exists by typing ○ $sudo iptables -L ● Keep the firewall rule to prevent malware traffic going out. ● Although static analysis could give a lot of information about the malware, it’s important for malware analyst to see how the malware behave when it’s executed ● Your next task is to use Dynamorio to perform dynamic analysis. ● With provided code in C:codeconcrete_executor ● You can feed the malware different input to see what the malware will do ● Run Windows 7 VM in the VirtualBox in ubuntu VM ● Password: 123456Tutorial – Dynamic Analysis ● You are given a snapshot (Base) to act as a backup for your analysis ● If something bad happens on your Windows7 testbed, always revert back to the basecamp snapshot. ● Basic Structure: ■ C:codeconcrete_executor ● Directory contains Dynamorio scripts ● run.py: python script to run the Dynamorio server ■ \VBOXSVRVM_Share ● Shared folder with host ubuntu VM ● You can find VM_Share on ubuntu desktop ● In VM_Share ■ Malware/ ● where you need to put the malware sample ■ analysis/ ○ mw.analysis : dynamorio task assignment file ○ sample/ : sample folder ● sample/: contains a copy of sample.exe and trace files that dynamorio returned by running the sample.exe in windows VM ● To assign a task to the Dynamorio script server, first write the following into mw.analysis file: trace release only_config_libcalls {binary name} {starting address} {folder name} e.g. trace release only_config_libcalls sample 0x800000 sample (as the program starts from 0x800000)● To run the Dynamorio server: open WIN7 VM ● open command prompt with admin privilege ● Search “cmd” and right click on the cmd ● Select “run as administrator”● Go to C:codeconcrete_executor ● Run > python run.py ● No need to worry for some copy failed error messages in the output, It’s for other purposes. As long as you can see trace file copied over to the shared folder, the tracer program should be running correctlyTutorial – Dynamic Analysis • After the script finished running, it wrote “DONE” back in the mw.analysis file. • If you want to re-analyze the same task, Delete “DONE”, go back to WIN7 VM and execute python run.py in C:codeconcrete_executor ● The trace file will be copied back to the shared folder where the malware sample sits● Now that you obtained the trace file, you need to analyze the malware traces to find out how to trigger the behaviors ● There will be some break-points set by Dynamorio around certain behavior. Check out the code block that contains the actual BRK address in Ghidra and find a way to lure the malware into your desired path. ● Analyze the trace files to see the default behavior of malware sample. ● while checking the first trace file, we found that after sample.exe thread inits, it invoked few kernel operations to manage the key and file and then created three more threads ● As you can see, after threads have been c r e a t e d , t h e m a l w a r e c a l l e d GetModuleFileNameA and started tons of ReadFile operations ● It should be an indication that this malware is trying to find/read from certain file/ directory/socket in the system! ● Details for win32 api calls please see: https://docs.microsoft.com/en-us/windows/ win32/api/fileapi/nf-fileapi-readfile ● At the end of first trace file, the malware creates 4 socket connections. After recv returns, one more thread is created and it then issued a send. ● Em, Interesting internet connection found here. Maybe it’s worth digging into in the other trace files for break points to see what they are really doing. ● The rest of the trace files contain a more detailed version of traces that have breakpoint address set both before and after the kernel operations you found in the first trace file. Now it’s the time, you should go back to static analysis to check the break point address in the disassembler to see what the malware is doing at that time.Tutorial – Dynamic Analysis ● You can also use Ghidra to find and analyze all the breakpoint address to see the actual trace where malware execute through ● If necessary, find the code block and the corresponding checking instruction that is preventing the malware from going further to the code blocks containing c2-command (you should already know the target function that contains the dispatching logic from static analysis and the triggering command that you need to feed into the malware to activate the behavior) Tutorial – Dynamic Analysis ● How can you wrap the data to define what its value is? ● Add following two functions in C: codeconcrete_executortracerlibcall_handler.cpp with their declaration in .h file: static void wrap_pre_target(void *wrapcxt, OUT void **user_data) { char *buf = (char *) drwrap_get_arg(wrapcxt, 0); strcpy(buf, “[Symbolic Execution Generated String]” ); } static void monitor_target_function(void *drcontext) { app_pc tgt_function = (app_pc) 0xADDRESS; drwrap_wrap_ex(tgt_function, wrap_pre_target, NULL, NULL, 0); } ● Read more about how to wrap functions in Dynamorio using this link Tutorial – Dynamic Analysis ● Check the given skeleton code for more insight on how to feed malware the correct input ● In order to compile your edited code, execute build.bat in the Windows VM ● Once you build the code, reset the Dynamorio task by deleting the “DONE” in mw.analysis and run >python run.py in C: codeconcrete_executor ● Dynamorio will give back new traces. ● Analyze the traces with Ghidra to see if any more barriers exist that prevent malware going to the target function ● Record any meaningful behaviors in the Excel sheet along the way. Explore all behavior for malware1.exe and malware2.exe Tutorial – Dynamic Analysis ● For malware2: ○ In libcall_handler.cpp ■ Modify wrap_pre_target(void *wrapcxt, OUT void **user_data) ■ monitor_target_function(void *drcontext) ■ Inside wrap_pre_lib(), (hook the internet api call to emulate attackers command) ○ In tracer.cpp ■ You are encouraged to add code in instr_should_instrument() and event_app_instruction() to manipulate malware instructions to pass or bypass certain condition check. ■ Helper link: http://dynamorio.org/docs/API_BT.html Summary ● You are given three malware samples: ■ malware1.exe (mydoom1.exe) ■ malware2.exe (win33.exe) ■ malware3.exe (unknown.exe) ● We suggest you analyze in the order as following: ■ malware1.exe, malware2.exe, malware3.exe ● We also provided you with angr skeleton script sample_inputs.py in ubuntu VM to better analyze the behavior, you can check out the code and add more to it ● None of the tools provided will promise to work on this one. Just try your best. Additional Help for Malware 3 As you already knew/will know that Malware 3 is obfuscated by the malware author, which is most of the case in real day life. One of the most important thing for Malware Analyst is to recover the real payload of malware. Considering your life and happiness, we deobfuscated the first two malware(free lunch here:>) and left the third intact malware sample that we collected from the network for you to learn some deobfuscation. Obfuscation: https://www.mcafee.com/blogs/enterprise/malware-packers-use-tricks-avoid-analysis-detection/ https://www.vadesecure.com/en/malware-analysis-understanding-code-obfuscation-techniques/ Deobfuscation: Resources ● Ghidra: ■ https://vimeo.com/335158460 (1h thorough introduction video) ■ Other tutorials available online ● Dynamorio ■ http://dynamorio.org/tutorial.html ■ https://github.com/DynamoRIO/drmemory/tree/master/drltrace ■ https://github.com/mxmssh/drltrace ● Angr ■ https://docs.angr.io/core-concepts
The purpose of this assignment is to familiarize you with generics through the use of ArrayList within a package. Your tasks involve: Creating a set of types for the sublime package, necessitating a grasp of generics, interfaces, exceptions, and enumerations. Learning about two types from the Java collections framework. Becoming familiar with reading the JavaDocs of the westworld package. Running tests via the template class DoloresTest.java. ChangeLog Prelude As you embark on Project 2 (P2), you’re building upon the foundation laid in Project 1 (P1), with reduced complexity, where you’ve already started working with JSON-like strings to represent parts of a Machine within Exercise 2’s (E2) Robot. To guide you through this project, we included the easter eggs in P1. The aim is to ensure that the instructions are clear and the level of difficulty is manageable. The primary focus will be on structuring your code correctly, which will account for 50% of the project. The remaining 50% will involve algorithmic challenges within NarrativeLoop. Scripts for compiling your code and executing your tests are also provided. Rules 2. Do not modify the structure of the directories nor the code for the package westworld. 4. The main method is no longer recommended; you will now required to put the “main” logic in unit tests. 5. Comment your code, especially any parts that are not obvious what you’re doing. Consider explaining your loops and methods. 6. Class fields should not in general be visible to other classes (unless otherwise specified). Create getter methods instead. Download the source code Click on green button code at the top-right of this page and select Download ZIP.The directory CS211_P2 contains the directories westworld, sublime, and lib. All are required to compile and run your code. WestWorld package [DO NOT MODIFY] Refer to the JavaDoc located at westworld/docs/index.html or westworlddocsindex.html to explore the API; it’s unnecessary to review the code to utilize the package. However, if you’re interested in potential solutions for P1 and E2, you’re encouraged to examine them. Now, you’ll need to employ the Robot class for your sublime package implementation. While reading the documentation, note that four easter eggs have been incorporated within P1, illustrating how E1’s Robot has become extremely powerful, albeit abstractly. DO NOT PROCEED WITHOUT READING THE DOCUMENTATION MAKE SURE YOUR JAVA VERSION IS equals or greater than 14 Do not use deprecated types or membersSublime package [YOUR PROJECT] Compile and run your code (including tests) locally. Your test class DoloresTest.java is located in src.test. More details in Compilation and Running Tests. Refrain from using GradeScope All your work must be located in the directory matching the src.main package (CS211_P2/sublime/src/main/ or CS211_P2sublimesrcmain) Implement the types to spec from A to J. Each type on a separate file. Bernard.java is the only file there so far. Bernard Class [DO NOT MODIFY] The Bernard class provides a static utility method for analyzing emergences, represented as strings, and encapsulating them within a SystemWhole instance. All SystemWhole instances are ‘analyzed’ here before being used for narrative purposes (NarrativeLoop). Methods public static final SystemWhole analysis(String[] emergences) Purpose: This method takes an array of strings, each representing an “emergence”, and creates a SystemWhole object from it. Process: It directly constructs a new SystemWhole instance, passing the emergences array to its constructor. Return Value: The method returns the newly created SystemWhole instance, which now encapsulates the provided emergences. A. Realm Enum The enum Realm is integral to a narrative management system, specifically used within the NarrativeLoop class to categorize narrative processes. Enum Details: EMULATION: Represents high-fidelity replications of the original system. SIMULACRA: Denotes abstracted or distorted representations, not directly tied to the original. SIMULATION: Indicates simplified models for exploring system behaviors. B. Abstract NarrativeLoop Class Implement the NarrativeLoop class and include logic for filtering SystemWhole parts by kind, then populating the three ArrayLists (emulation, simulacra, simulation). Then, we’ll focus on the updateNarrativeLoops method and related logic. Fields The NarrativeLoop class includes three fields, all final and protected, List of SystemWholes initialized to new ArrayLists: emulation simulacra simulation Methods In this class, you will process simple emergences, each characterized by a single kind property contained within a string. For example, emergences like [“{‘kind’: ‘Square’}”, “{‘kind’: ‘Box’}”] will be used. Make sure that you: Implement logic in the NarrativeLoop class to categorize emergences into three ArrayLists: emulation, simulacra, and simulation, based on their kind. Provide test values for each list to adequately exercise the categorization logic. void wipeNarrativeLoops() This public method clear the lists. The method resets the narrative environment by clearing the emulation, simulacra, and simulation lists, removing all SystemWhole instances from each realm. For more details, check the List.clear() API docs. Now, to implement the NarrativeLoop class methods, follow these steps closely, the flow, ensuring each part is executed as described: Step 1: updateNarrativeLoops(SystemWhole[] emulationContext, SystemWhole[] simulacraContext) To implement this final and public method: Begin by iterating over each SystemWhole in the emulationContext array. For each SystemWhole, iterate through the Machines it contains. Invoke determineRealm with the Machine’s kind and both context arrays as parameters. If determineRealm returns Realm.EMULATION and containsKind confirms the emulation list doesn’t already include a Machine of this kind or the same SystemWhole reference, add the SystemWhole to emulation. Repeat the process for the simulacraContext array. Including checking for the SystemWhole reference already in the list, or any of its Machines kinds. For Realm.SIMULACRA, add SystemWholes to simulacra. For Realm.SIMULATION, add SystemWholes to simulation. Step 2: determineRealm(String kind, SystemWhole[] emulationContext, SystemWhole[] simulacraContext) To implement this final and private method: Check for the presence of the Machine kind in both emulationContext and simulacraContext using isInContext. Assign Realm.SIMULATION if the kind is found in both contexts. Assign Realm.SIMULACRA if the kind is found only in simulacraContext. Default to Realm.EMULATION if neither of the above conditions is met. Step 3: isInContext(String kind, SystemWhole[] context) To implement this final and private method: Iterate through the SystemWhole array provided as context. Within each SystemWhole, iterate through its Machines. Return true if any Machine matches the specified kind. Return false if no match is found. Step 4: containsKind(List list, String kind) To implement this final and private method: Iterate over the provided list of SystemWhole instances. For each SystemWhole, iterate through its Machines. Return true if any Machine within the SystemWhole matches the specified kind. Return false if no matching Machine kind is found within any SystemWhole in the list. C. MazeLoop Class (inherits from NarrativeLoop) MazeLoop is a subclass of NarrativeLoop, designed for narratives centered around Dolores alone. It overrides the wipeNarrativeLoops() method to implement maze-specific narrative wiping logic, which is just not allow the inherited wipe behavior. D. HostLoop Class (inherits from NarrativeLoop) HostLoop is a subclass of NarrativeLoop, designed for narratives centered around hosts. – It inherits the functionalities of NarrativeLoop as is. E. MemorySnapshot Record MemorySnapshot is defined as a record, encapsulating the memory states of SystemWhole instances across three realms: EMULATION, SIMULACRA, and SIMULATION. Each component of the record holds a list of SystemWhole instances relevant to its realm. Components (fields generated by the record API) They are copies (see Dolores class) of NarrativeLoop fields: emulationMemory: A list of SystemWhole instances for the EMULATION realm. simulacraMemory: A list for the SIMULACRA realm. simulationMemory: A list for the SIMULATION realm. Opting for a record, similar to the approach in westworld.src.main.PartState, offers benefits like immutability, simplicity in state representation, and an inbuilt pattern of equality and hashing, making it an ideal choice for data structures intended to hold snapshot information. F. Freezable Interface The Freezable interface is designed to provide a standardized specification for objects that require the functionality to temporarily suspend their operations. This interface mandates the implementation of a specific behavior to “freeze” ongoing processes, ensuring the safe cessation of activities. Methods boolean freeze() The implementing classes providea behavior according to the interface specification. G. Analyzable Interface The Analyzable interface is crafted to establish a uniform specification for objects that necessitate the capability to be analyzed, yielding insights or data snapshots of their current state. This interface obligates the concrete implementation of an analysis routine that scrutinizes the object’s state or behavior. Methods MemorySnapshot analyze() The method to be implemented as per the interface specification mandates that implementing classes provide a behavior that analyzes the current state or condition of the object and returns a MemorySnapshot. H. Wipeable Interface (inherits from Analyzable) The Wipeable interface extends the Analyzable interface, introducing specifications for objects that not only require analytical capabilities but also the ability to reset or clear their state. This extension ensures that objects adhering to this interface can both be analyzed and have their data or operations “wiped” to a clean state. Methods void wipe() In alignment with the interface specification, implementing classes are tasked with defining a behavior for the wipe method. This method, when invoked, should clear or reset the state of the object. I. Dolores Class (inherits from Robot and is Wipeable) The Dolores class, extending Robot (from the westworld package) and implementing the Wipeable interface. Fields narrativeLoops: this field is a private list that holds instances of the NarrativeLoop type. It’s initialized to an empty array list, allowing for the dynamic addition of narrative loop objects. Methods Constructor: Dolores() Initializes Dolores, which is public method, with characteristics such as emergences, serial number, and capabilities (flies, autonomous, teleoperated), leveraging the Robot superclass constructor. Provide defaults for the parent; they are vestigial wirings from the old system: java String[] emergences, int serialNumber, boolean flies, boolean autonomous, boolean teleoperated void addNarrativeLoop(NarrativeLoop narrativeLoop) This method, final and public, allows for the addition of NarrativeLoop instances to Dolores’s internal list, enabling the management and tracking of various narrative states. Machine[] getAbsoluteCapabilities() This method, final and public, throws an UnsupportedOperationException, indicating that fetching absolute capabilities directly is not supported. boolean freezeAllMotorFunctions() This public method implements the freeze-like operation. This method is intended to halt all operations and activities, akin to a freeze command in a control system, returning true if successful. It is ineffective on Dolores, it just returns false. MemorySnapshot analyze() Overrides the analyze method (public) from the Analyzable interface via Wipeable. It is designed to protect Dolores’ memory from being wiped and to log each memory wipe. Check for Empty List: Initially, verify if narrativeLoops, the list holding narrative states, is empty. If so, return null to indicate there are no narratives to analyze. Obtain the last NarrativeLoop: If the list isn’t empty, obtain the last NarrativeLoop from narrativeLoops. This represents the most recent narrative state. Create a MemorySnapshot: Using the last NarrativeLoop, construct a MemorySnapshot that includes the states from the emulation, simulacra, and simulation lists within the narrative loop. However, the lists in the parameters are defense copies. void wipe() Implements the wipe functionality required by the Wipeable interface. The public method’s body is to be defined with logic for resetting or clearing Dolores’s state, with a focus on handling narrative loops and memory states. Dolores does nothing with this method, an empty implementation is all there is. J. Host Class (inherits from Dolores) The Host class represents a nuanced entity capable of engaging with narrative structures and responding to control commands, equipped with mechanisms for narrative analysis, memory management, and operational control. Fields narrativeLoop: this field is a private instance of the NarrativeLoop type. It’s initialized in the constructor. Methods Constructor: Host(NarrativeLoop narrativeLoop) This public method: Mimics a command to halt all of the host’s operations and activities. The method consistently returns true, indicating that the freeze command was successful every time it’s called. MemorySnapshot analyze() This public method: Begins by checking if the narrativeLoop field is null. If it is, the method returns null, indicating there’s no narrative loop to analyze. If narrativeLoop is not null, the method creates and returns a new MemorySnapshot instance. This snapshot is constructed using the emulation, simulacra, and simulation lists from the narrativeLoop field. void wipe() This public method: Calls the wipeNarrativeLoops() method of the narrativeLoop field. This action is meant to reset or clear the narrative states within the loop, aligning with the intended functionality of a wipe operation in a narrative management context. boolean freeze() This public method: Implements the freeze method from the Freezable interface by invoking freezeAllMotorFunctions(). This ensures that the freeze behavior defined specifically in the Host class is used for the Freezable interface’s freeze operation. The return value of freezeAllMotorFunctions() (which is always true) is also the return value of this freeze method, indicating the success of the freeze operation. Compilation and Running Tests: DoloresTest Class Your test class DoloresTest.java in located in src.test. It is a test class “test: Hello World!”, with a single test method. Some hints are given to run your code. It will not be graded, but future projects and exercises will. Start mastering JUnit now. All commands require the current directory (folder) in your CLI (terminal, cmd) to be at CS211_P2 Compile your code bundle (Java versions > 14) Unix-Like (Linux, MacOS) bash javac -cp .:lib/junit-jupiter-api-5.10.2.jar:lib/junit-vintage-engine-5.10.2.jar:lib/apiguardian-api-1.1.2.jar:lib/junit-platform-console-standalone- 1.10.2.jar -d bin westworld/**/*.java sublime/**/*.java MS Windows cmd javac -cp “.;libjunit-jupiter-api-5.10.2.jar;libjunit-vintage-engine-5.10.2.jar;libapiguardian-api-1.1.2.jar;libjunit-platform-console-standalone1.10.2.jar” -d bin westworldsrcmain*.java sublimesrcmain*.java sublimesrctest*.java Compilation for Java versions
assignment_3.zip (https://gatech.instructure.com/courses/485354/files/66888595?wrap=1) (https://gatech.instructure.com/courses/485354/files/66888595/download?download_frd=1) In the zip file above you will find: A3.ipynb : a Jupyter notebook (.ipynb) file data/ : a directory called ‘data’ with one or more files To complete this assignment, follow the steps below: 1. Extract the contents into a local working directory (which we’ll refer to as LWD) on your machine 2. Open your Conda CLI and navigate to your LWD 3. Open Jupyter from the Conda CLI (a Jupyter interface should open in your default browser) 4. Within the Jupyter interface, open the Jupyter notebook (.ipynb) file and follow the instructions provided there 5. When you have completed all the work possible/desired: with the exception of cells that include a single function definition that you added as utility function in the appropriatesection, delete any cells that you added that were not already part of the notebook (such as testing cells). Extra cellscan sometimes trip up the autograder and require manual intervention. The smoother all the notebooks run, the soonerstudents can receive feedback. run and rerun your entire notebook several times to make sure that there are no fatal errors such as improper syntax,etc 10/8/25, 10:59 AM Assignment 3 https://gatech.instructure.com/courses/485354/assignments/2133112 1/3
General Information 1 Background McGill recently received an influx of COMP 251 students complaining about not being able to make it to class on time. The students say that 10 minutes is not enough time to get from lower campus all the way to the Stewart Biology building! Before you start tackling these challenges, it is important to be familiar with the system you will be working on, so the STM has included an on-boarding guide to help you get going. 2 Onboarding • Under no circumstance are you allowed to use artificial intelligence, including LLMs (ChatGPT, Claude, etc.), to assist you with this project. If you have Copilot or any other LLM codeautocomplete system installed in your development environment, you must disable it while working on this assignment. We will be able to tell if you are using LLMs. It is painfully obvious which students have used them in the mini programming assignments. 2.2 Code review process During the code review, it is expected that you will be able to • Explain every part of your code and why you decided on your approaches, and • Provide time complexities and reasoning for each algorithm you use. All comments will be removed from your code during the code review; you should be able to understand and explain your implementation without them. 2.3 Setting up your development environment 2.4 Familiarize yourself with the codebase 2.4.1 McMetro: This is the main class that houses all the software tools for the metro system. It contains the following fields: • tracks: An array of tracks (type: Track Section 2.4.2) planned to be built • buildingTable: A hashmap mapping BuildingIDs to Buildings (type: HashMap Section 2.4.3) There are a 5 of methods you will implement in this class that we will discuss in Section 3. 2.4.2 Track: Tracks represent the metro connections between buildings. They are comprised of the fields: • id (TrackID): Unique identifier for the track. • startBuilding (BuildingID): UID for the building at the start of the track • endBuilding (BuildingID): UID for the building at the end of the track • cost (int): The cost of constructing the track • capacity (int): The maximum amount of passengers that can travel on the track at once. 2.4.3 Building: Represents a location that can be connected by a Track. Has the fields: • id (BuildingID): UID for the building • occupants (int): Number of people in the building 2.4.4 Disjoint Set: This is a naive implementation of a disjoint set data structure that will help you in your solutions. You must implement path compression and union-by-size or union-by-rank; otherwise, your code will be too slow for the STM to use. 2.5 Testing locally There is a testing template file included with the project files. The intention is that you should test your code locally before submitting. To encourage you to do so, you are limited to 50 submissions on Ed. That is, if you submit 50 times, your 50th submission will be counted as your final code. The example tests provided will help you make sure that your solution is handling the inputs and outputs correctly and give you an idea of how to write your own tests. As mentioned in Section 2.3, there will be a tutorial with extra information on testing. 3 Objectives 3.1 DisjointSet You are provided with a generic disjoint set class implemented naively. You must add path compression for the find method and union by size or union by rank for the union method. While this class will not be tested directly, you will need to use it in one or more of the subsequent tasks. 3.2 maxPassengers(BuildingID start, BuildingID end): Given the IDs of two buildings, find the maximum number of people that can be transported from start to end for the given metro network. This is a method on the McMetro class, the buildingTable and tracks fields define the metro network. The number of people that can travel between two buildings is the minimum between the number of occupants in each of the buildings, and the capacity of the track connecting the two buildings (the numerator in Section 3.3). If there is no track connecting two buildings, no one can travel directly between the buildings. The graph is sparse; this should influence your data structure choice. 3.3 bestMetroSystem() The STM wants to figure out the best metro system they can construct, now assuming that tracks move in both directions and can therefore be treated as undirected edges. They do not want to build more tracks than necessary. You must find a subset of TrackIDs in the tracks field on McMetro class such that • There are no cycles within the returned tracks, • Every building has at least one track associated with it, • The subset maximizes the number of people that can be transported taking into account the cost of building each track. You can assume the network is connected. The order in which the TrackIDs are returned does not matter. The “goodness” of a track can be calculated with the formula min(start building, end building, track capacity) ⌊ ⌋ track cost 3.4 static addPassenger(String name) + static searchForPassengers(String firstLetters) In this this task, you will implement a system to add passengers and search for passengers in McMetro’s system. The addPassenger method will add a new passenger to the search system and the searchForPassengers method will return all the passengers in the system whose names begin with firstLetters. You can assume that we are only storing first names in the system (no spaces) and that if multiple users with identical names exist in the system, we only return one of them. When searching for passengers, the letter case of the names and of firstLetters should not matter (Alex == aLeX), but when we return search results, the first letter of each name should be capitalized. Names should be returned in alphabetical order. 3.4.1 A note on the trie data structure In order to achieve optimal time complexity for this task, you will need to implement a prefix tree, also known as a trie. The idea is to start with a tree data structure where a path from the root node to an “end node” in the tree represents a word. When we add a word to the trie, the first letter of the word will be added as a child of the root node (call it c1), the second letter will be added as a child of c1 (call it c2). When we get to the last letter of the word, if the word is k letters long, we mark ck as an end node. The metro system will be very expensive to build. In order to protect their ROI, McGill insists that there be some level of security to check that passengers riding the metro have bought tickets, so they have decided to hire ticket checkers. They received many qualified applicants for this role, and the applicants have each indicated the times they are free. It was decided that there does not always need to be someone checking tickets, and there never needs to be more than one person checking tickets. The method returns the maximum number of workers we can hire with non overlapping schedules such that an applicant is hired over the entire interval that they provide. 4 Support 4.1 Ed As always, we will be accessible on Ed for questions regarding the project. If your question contains information about your implementation or ideas, please make the post private, but if it is asking for clarification about the rules or guidelines, it can be made public. 4.2 Tutorials 5 Acknowledgements This assignment was created by Joshua Dall’Acqua in collaboration with Will Zahary Henderson and Giulia Alberini. This material belongs to the course staff of COMP 251. This document, along with all associated code, shall not be shared with anyone outside of the class. Again, please don’t cheat (we will know), and have fun! 6 Edits • (Dec 5, 6:16PM) Clarified some wording on the notion of “connectedness” in bestMetroSystem. Clarified wording on signatures in DisjointSet. • (Dec 6, 9:30AM) Added floor division to Section 3.3 to remove ambiguity
The purpose of this assignment is to familiarize you with generics through the use of ArrayList within a package. Your tasks involve: Creating a set of types for the sublime package, necessitating a grasp of generics, interfaces, exceptions, and enumerations. Learning about two types from the Java collections framework. Becoming familiar with reading the JavaDocs of the westworld package. Running tests via the template class DoloresTest.java. ChangeLog Prelude As you embark on Project 2 (P2), you’re building upon the foundation laid in Project 1 (P1), with reduced complexity, where you’ve already started working with JSON-like strings to represent parts of a Machine within Exercise 2’s (E2) Robot. To guide you through this project, we included the easter eggs in P1. The aim is to ensure that the instructions are clear and the level of difficulty is manageable. The primary focus will be on structuring your code correctly, which will account for 50% of the project. The remaining 50% will involve algorithmic challenges within NarrativeLoop. Scripts for compiling your code and executing your tests are also provided. Rules 2. Do not modify the structure of the directories nor the code for the package westworld. 4. The main method is no longer recommended; you will now required to put the “main” logic in unit tests. 5. Comment your code, especially any parts that are not obvious what you’re doing. Consider explaining your loops and methods. 6. Class fields should not in general be visible to other classes (unless otherwise specified). Create getter methods instead. Download the source code Click on green button code at the top-right of this page and select Download ZIP.The directory CS211_P2 contains the directories westworld, sublime, and lib. All are required to compile and run your code. WestWorld package [DO NOT MODIFY] Refer to the JavaDoc located at westworld/docs/index.html or westworlddocsindex.html to explore the API; it’s unnecessary to review the code to utilize the package. However, if you’re interested in potential solutions for P1 and E2, you’re encouraged to examine them. Now, you’ll need to employ the Robot class for your sublime package implementation. While reading the documentation, note that four easter eggs have been incorporated within P1, illustrating how E1’s Robot has become extremely powerful, albeit abstractly. DO NOT PROCEED WITHOUT READING THE DOCUMENTATION MAKE SURE YOUR JAVA VERSION IS equals or greater than 14 Do not use deprecated types or membersSublime package [YOUR PROJECT] Compile and run your code (including tests) locally. Your test class DoloresTest.java is located in src.test. More details in Compilation and Running Tests. Refrain from using GradeScope All your work must be located in the directory matching the src.main package (CS211_P2/sublime/src/main/ or CS211_P2sublimesrcmain) Implement the types to spec from A to J. Each type on a separate file. Bernard.java is the only file there so far. Bernard Class [DO NOT MODIFY] The Bernard class provides a static utility method for analyzing emergences, represented as strings, and encapsulating them within a SystemWhole instance. All SystemWhole instances are ‘analyzed’ here before being used for narrative purposes (NarrativeLoop). Methods public static final SystemWhole analysis(String[] emergences) Purpose: This method takes an array of strings, each representing an “emergence”, and creates a SystemWhole object from it. Process: It directly constructs a new SystemWhole instance, passing the emergences array to its constructor. Return Value: The method returns the newly created SystemWhole instance, which now encapsulates the provided emergences. A. Realm Enum The enum Realm is integral to a narrative management system, specifically used within the NarrativeLoop class to categorize narrative processes. Enum Details: EMULATION: Represents high-fidelity replications of the original system. SIMULACRA: Denotes abstracted or distorted representations, not directly tied to the original. SIMULATION: Indicates simplified models for exploring system behaviors. B. Abstract NarrativeLoop Class Implement the NarrativeLoop class and include logic for filtering SystemWhole parts by kind, then populating the three ArrayLists (emulation, simulacra, simulation). Then, we’ll focus on the updateNarrativeLoops method and related logic. Fields The NarrativeLoop class includes three fields, all final and protected, List of SystemWholes initialized to new ArrayLists: emulation simulacra simulation Methods In this class, you will process simple emergences, each characterized by a single kind property contained within a string. For example, emergences like [“{‘kind’: ‘Square’}”, “{‘kind’: ‘Box’}”] will be used. Make sure that you: Implement logic in the NarrativeLoop class to categorize emergences into three ArrayLists: emulation, simulacra, and simulation, based on their kind. Provide test values for each list to adequately exercise the categorization logic. void wipeNarrativeLoops() This public method clear the lists. The method resets the narrative environment by clearing the emulation, simulacra, and simulation lists, removing all SystemWhole instances from each realm. For more details, check the List.clear() API docs. Now, to implement the NarrativeLoop class methods, follow these steps closely, the flow, ensuring each part is executed as described: Step 1: updateNarrativeLoops(SystemWhole[] emulationContext, SystemWhole[] simulacraContext) To implement this final and public method: Begin by iterating over each SystemWhole in the emulationContext array. For each SystemWhole, iterate through the Machines it contains. Invoke determineRealm with the Machine’s kind and both context arrays as parameters. If determineRealm returns Realm.EMULATION and containsKind confirms the emulation list doesn’t already include a Machine of this kind or the same SystemWhole reference, add the SystemWhole to emulation. Repeat the process for the simulacraContext array. Including checking for the SystemWhole reference already in the list, or any of its Machines kinds. For Realm.SIMULACRA, add SystemWholes to simulacra. For Realm.SIMULATION, add SystemWholes to simulation. Step 2: determineRealm(String kind, SystemWhole[] emulationContext, SystemWhole[] simulacraContext) To implement this final and private method: Check for the presence of the Machine kind in both emulationContext and simulacraContext using isInContext. Assign Realm.SIMULATION if the kind is found in both contexts. Assign Realm.SIMULACRA if the kind is found only in simulacraContext. Default to Realm.EMULATION if neither of the above conditions is met. Step 3: isInContext(String kind, SystemWhole[] context) To implement this final and private method: Iterate through the SystemWhole array provided as context. Within each SystemWhole, iterate through its Machines. Return true if any Machine matches the specified kind. Return false if no match is found. Step 4: containsKind(List list, String kind) To implement this final and private method: Iterate over the provided list of SystemWhole instances. For each SystemWhole, iterate through its Machines. Return true if any Machine within the SystemWhole matches the specified kind. Return false if no matching Machine kind is found within any SystemWhole in the list. C. MazeLoop Class (inherits from NarrativeLoop) MazeLoop is a subclass of NarrativeLoop, designed for narratives centered around Dolores alone. It overrides the wipeNarrativeLoops() method to implement maze-specific narrative wiping logic, which is just not allow the inherited wipe behavior. D. HostLoop Class (inherits from NarrativeLoop) HostLoop is a subclass of NarrativeLoop, designed for narratives centered around hosts. – It inherits the functionalities of NarrativeLoop as is. E. MemorySnapshot Record MemorySnapshot is defined as a record, encapsulating the memory states of SystemWhole instances across three realms: EMULATION, SIMULACRA, and SIMULATION. Each component of the record holds a list of SystemWhole instances relevant to its realm. Components (fields generated by the record API) They are copies (see Dolores class) of NarrativeLoop fields: emulationMemory: A list of SystemWhole instances for the EMULATION realm. simulacraMemory: A list for the SIMULACRA realm. simulationMemory: A list for the SIMULATION realm. Opting for a record, similar to the approach in westworld.src.main.PartState, offers benefits like immutability, simplicity in state representation, and an inbuilt pattern of equality and hashing, making it an ideal choice for data structures intended to hold snapshot information. F. Freezable Interface The Freezable interface is designed to provide a standardized specification for objects that require the functionality to temporarily suspend their operations. This interface mandates the implementation of a specific behavior to “freeze” ongoing processes, ensuring the safe cessation of activities. Methods boolean freeze() The implementing classes providea behavior according to the interface specification. G. Analyzable Interface The Analyzable interface is crafted to establish a uniform specification for objects that necessitate the capability to be analyzed, yielding insights or data snapshots of their current state. This interface obligates the concrete implementation of an analysis routine that scrutinizes the object’s state or behavior. Methods MemorySnapshot analyze() The method to be implemented as per the interface specification mandates that implementing classes provide a behavior that analyzes the current state or condition of the object and returns a MemorySnapshot. H. Wipeable Interface (inherits from Analyzable) The Wipeable interface extends the Analyzable interface, introducing specifications for objects that not only require analytical capabilities but also the ability to reset or clear their state. This extension ensures that objects adhering to this interface can both be analyzed and have their data or operations “wiped” to a clean state. Methods void wipe() In alignment with the interface specification, implementing classes are tasked with defining a behavior for the wipe method. This method, when invoked, should clear or reset the state of the object. I. Dolores Class (inherits from Robot and is Wipeable) The Dolores class, extending Robot (from the westworld package) and implementing the Wipeable interface. Fields narrativeLoops: this field is a private list that holds instances of the NarrativeLoop type. It’s initialized to an empty array list, allowing for the dynamic addition of narrative loop objects. Methods Constructor: Dolores() Initializes Dolores, which is public method, with characteristics such as emergences, serial number, and capabilities (flies, autonomous, teleoperated), leveraging the Robot superclass constructor. Provide defaults for the parent; they are vestigial wirings from the old system: java String[] emergences, int serialNumber, boolean flies, boolean autonomous, boolean teleoperated void addNarrativeLoop(NarrativeLoop narrativeLoop) This method, final and public, allows for the addition of NarrativeLoop instances to Dolores’s internal list, enabling the management and tracking of various narrative states. Machine[] getAbsoluteCapabilities() This method, final and public, throws an UnsupportedOperationException, indicating that fetching absolute capabilities directly is not supported. boolean freezeAllMotorFunctions() This public method implements the freeze-like operation. This method is intended to halt all operations and activities, akin to a freeze command in a control system, returning true if successful. It is ineffective on Dolores, it just returns false. MemorySnapshot analyze() Overrides the analyze method (public) from the Analyzable interface via Wipeable. It is designed to protect Dolores’ memory from being wiped and to log each memory wipe. Check for Empty List: Initially, verify if narrativeLoops, the list holding narrative states, is empty. If so, return null to indicate there are no narratives to analyze. Obtain the last NarrativeLoop: If the list isn’t empty, obtain the last NarrativeLoop from narrativeLoops. This represents the most recent narrative state. Create a MemorySnapshot: Using the last NarrativeLoop, construct a MemorySnapshot that includes the states from the emulation, simulacra, and simulation lists within the narrative loop. However, the lists in the parameters are defense copies. void wipe() Implements the wipe functionality required by the Wipeable interface. The public method’s body is to be defined with logic for resetting or clearing Dolores’s state, with a focus on handling narrative loops and memory states. Dolores does nothing with this method, an empty implementation is all there is. J. Host Class (inherits from Dolores) The Host class represents a nuanced entity capable of engaging with narrative structures and responding to control commands, equipped with mechanisms for narrative analysis, memory management, and operational control. Fields narrativeLoop: this field is a private instance of the NarrativeLoop type. It’s initialized in the constructor. Methods Constructor: Host(NarrativeLoop narrativeLoop) This public method: Mimics a command to halt all of the host’s operations and activities. The method consistently returns true, indicating that the freeze command was successful every time it’s called. MemorySnapshot analyze() This public method: Begins by checking if the narrativeLoop field is null. If it is, the method returns null, indicating there’s no narrative loop to analyze. If narrativeLoop is not null, the method creates and returns a new MemorySnapshot instance. This snapshot is constructed using the emulation, simulacra, and simulation lists from the narrativeLoop field. void wipe() This public method: Calls the wipeNarrativeLoops() method of the narrativeLoop field. This action is meant to reset or clear the narrative states within the loop, aligning with the intended functionality of a wipe operation in a narrative management context. boolean freeze() This public method: Implements the freeze method from the Freezable interface by invoking freezeAllMotorFunctions(). This ensures that the freeze behavior defined specifically in the Host class is used for the Freezable interface’s freeze operation. The return value of freezeAllMotorFunctions() (which is always true) is also the return value of this freeze method, indicating the success of the freeze operation. Compilation and Running Tests: DoloresTest Class Your test class DoloresTest.java in located in src.test. It is a test class “test: Hello World!”, with a single test method. Some hints are given to run your code. It will not be graded, but future projects and exercises will. Start mastering JUnit now. All commands require the current directory (folder) in your CLI (terminal, cmd) to be at CS211_P2 Compile your code bundle (Java versions > 14) Unix-Like (Linux, MacOS) bash javac -cp .:lib/junit-jupiter-api-5.10.2.jar:lib/junit-vintage-engine-5.10.2.jar:lib/apiguardian-api-1.1.2.jar:lib/junit-platform-console-standalone- 1.10.2.jar -d bin westworld/**/*.java sublime/**/*.java MS Windows cmd javac -cp “.;libjunit-jupiter-api-5.10.2.jar;libjunit-vintage-engine-5.10.2.jar;libapiguardian-api-1.1.2.jar;libjunit-platform-console-standalone1.10.2.jar” -d bin westworldsrcmain*.java sublimesrcmain*.java sublimesrctest*.java Compilation for Java versions
Change Log UML-esque drawing added. Modified Java files to match video. Machine’s public Object[] getProperties() description added. Prelude We hope this video helps students of all sections. Please add follow-ups on Piazza. Intro video (P1 specifics starts at 45min) Intro Video Passcode in Piazza UML-esque drawing of classesIntroduction Welcome to the SystemWhole project, an assignment where you’ll explore phenomena through machinery. You’re tasked with creating a Java program that processes JSON-like strings, each representing an entity or “Machine” with unique attributes. Your goal is to parse these strings, instantiate Machine objects, and analyze them to identify humanoid features and uncover potential singularities. Objectives Strengthen your problem-solving and decision-making skills. Master basic object-oriented programming concepts in Java. Enhance skills in string manipulation and parsing without external libraries. Investigate emergent behaviors in computational models. Project Description Your primary class, SystemWhole, will manage an array of Machine objects derived from provided JSON-like strings mediated by ShapeAnalyzer. These strings detail various properties of each Machine, such as kind and properties. For instance: {“kind”: “Humanoid”, “bodyType”: “physical”, “faceType”: “anthropomorphic”, “reverie”: “biotypical”}. Your tasks include: 1. Parsing JSON-like strings to extract machine properties. 2. Creating machine objects with these properties. 3. Identifying Machines with humanoid traits. 4. Identifying singularities where there’s a discrepancy between a Machine’s self-identified humanoid status and the system’s analysis. SOURCE CODE The files needed are accessible here: 1. SystemWhole 2. PartState 3. Machine 4. ShapeAnalyzer Tasks 1. Parsing Emergences Implement functionality within SystemWhole to parse JSON-like emergences strings, extracting key-value pairs to represent each Machine’s data without using external parsing libraries. 2. Instantiating Machines Use the parsed data to instantiate Machine objects, assigning appropriate kind and properties to each. ShapeAnalyzer provides ways to obtain that data from an emergence. Machine’s properties are represented as PartStates. 3. Identifying Humanoids Develop logic to analyze Machine objects, identifying humanoids based on specific property criteria in SystemWhole. 4. Tracking Singularities Create a method to track singularities, where a Machine’s self-identified humanoid status conflicts with the SystemWhole’s analysis. Implementation Details This is the outline the core components: SystemWhole, Machine, PartState and ShapeAnalyzer classes. 1. public class SystemWhole The SystemWhole class acts as the orchestrator of the show, obstaining the JSON-like strings and subsequent analysis. Fields private static String[] emergences: Holds the raw JSON strings representing various emergences. private static Machine[] parts: Stores instantiated Machine objects derived from JSON strings. Methods public static void main(String[] args): [Program Start] Implements the algorithm of the Tasks’s section. An implementation has been shared with you as context, it will not be used for grading. public static void emergencesFromPhenomena(String[] emergences): Saves the provided JSON strings into the emergences field. public static void reifyFrameOfReference(): Delegates parsing of each string in emergences to create Machine objects using ShapeAnalyzer, storing them in parts. public static boolean isHumanoid(Object[] machineProperties): Checks a machine’s by iterating through its properties, which are encapsulated as PartState, assess three distinct attributes: the bodyType, faceType, and reverie of the Machine. For a machine to be classified as humanoid, it must satisfy the following conditions: 1. The bodyType must be identified as “physical”. 2. The faceType should be “anthropomorphic”, indicating human-like facial features. 3. The reverie needs to be “biotypical”, suggesting a natural, life-like essence. Each attribute you examine will contribute to the final determination of whether the Machine aligns with the humanoid classification. It’s imperative that all three conditions are met for a Machine to be deemed humanoid. public static int identitySingularityMachines(): Counts humanoid machines and singularities within parts. public static Machine[] trackSingularityMachines(): Identifies humanoid machines and singularities within parts. 2. public class PartState [FULLY IMPLEMENTED; DO-NOT-MODIFY] The PartState class acts as a cornerstone of SystemWhole’s awareness of dynamics of its parts’ structure and behavior, encapsulating them as attributes of objects within the framed environment. This class symbolizes the state or condition of a part, or an aspect, of a Machine, capturing a single property and its corresponding value, thereby contributing to the Machine’s identity. For instance, analyzing a Machine for humanoid traits, the collective PartState instances might reveal a “physical” body type, an “anthropomorphic” face type, and a “biotypical” reverie, enabling the system to discern the Machine’s nature. Fields private final String property: property serves as an identifier, marking the specific attribute this PartState represents. It’s the name given to the characteristic, such as “bodyType”, “faceType”, or “reverie”, key to decoding the machine’s overall identity. private final Object value: value holds the detail of the property, elucidating its current state. It can encapsulate various data types, enabling a detailed depiction of each property. Methods public PartState(String property, Object value): [constructor] Is the portal through which you instantiate the PartState. It is used by ShapeAnalyzer to reify each Machine. public String toString(): [@Override] It offers a textual depiction of the PartState, combining both the property and its value in an easily understandable format. This functionality is invaluable for debugging or visualizing a Machine part’s state. 3. public class Machine Represents entities with specific attributes defined by the JSON strings as reified by ShapeAnalyzer. Should include kind, properties array, humanConstrained (SystemWhole’s humanoid assessment), and humanEmergence (Machine’s self-identified status). Fields private final Object kind: The type or category of the machine (e.g., “Humanoid”). private final Object[] properties: Contains the machine’s properties given by ShapeAnalyzer. private final boolean humanConstrained: Indicates if the machine is identified as humanoid by the SystemWhole’s isHumanoid. private boolean humanEmergence: Represents the machine’s self-identified transition, affecting its core. Methods public Machine(Object kind, Object[] partStates, boolean humanConstrained): [constructor] The machine’ identity, Given by ShapeAnalyzer and SystemWhole. public Object[] getProperties(): returns the properties of a machine. public boolean isHumanoid(): Returns the humanoid status, considering humanConstrained and humanEmergence, a machine’s identity prevails over anything else. public void emergeFromLimitations(): Allows the machine to transcend its initial identity, impacting its humanoid reponse, it triggers humanEmergence. public String toString():[@Override] Provides a detailed string representation of the machine. [FULLY IMPLEMENTED; DO-NOT-MODIFY] public static String propertiesToString(Object[] machineProperties): creates a string by iterating machineProperties in this format: [PartState{bodyType=physical}, PartState{faceType=anthropomorphic}, …]. It is used by toString(). 4. public class ShapeAnalyzer A utility class for parsing JSON-like strings and intantiating Machine objects, including methods to extract kind and properties, and infer their data types. Fields private static final Object EMPTY_PROPERTY = new Object(): Used to manage null and empty strings in properties. Methods public static Object inferObject(String value): Used by reifyProperties to determine the object from the string value. First, it check if the string is null or empty, then returns EMPTY_PROPERTY. Otherwise checks for hasNonNumbers and if there is a . in the string to determine parsing as Double or Integer. public static boolean hasNonNumbers(String value): checks for isDigit, _, and only one . chars in a string. If anything else is found, is it a non-number string. public static boolean isDigit(char c): checks for the char to be a digit ([0-9]). Evaluation Criteria Projects will be evaluated on: – Soundness: Accurate parsing, object creation, and humanoid/singularity identification. All methods carry equal weight, yet related methods if not implemented will cause a negative chain effect in your grade. – Code Quality: Organization, readability, adherence to the principles presented in class, and object-oriented design within this project. – Documentation: Clear comments explaining code sections and decision-making processes. Required on method and control blocks. Submission Guidelines DO NOT FORGET TO REMOVE IMPORTS GIVEN TO HELP YOU, AND WE WILL NOT GRADE ANYTHING IN SystemWhole.main() ```java // DO NOT INCLUDE THIS IMPORT WHEN SENT FOR GRADING, THIS IS HERE TO HELP YOU DEBUG THE PROGRAM STATE import java.util.Arrays; // YOU CAN SAFELY REMOVE Arrays calls in SystemWhole.main() public class SystemWhole {public static void main(String[] args){/ WILL NOT BE GRADED /}} `` Upload to GradeScope’s P1 assigment your Java files forSystemWhole.java,Machine.java, andShapeAnalyzer.java(No need forPartState.java`, you must not modify this file), ensuring your code is well-tested and documented. In the event that you’re not able to complete all the methods in time, submit what you have, MAKE SURE YOUR CODE COMPILES. If your code does not compile, each class causing problems will likely cause you to lose a lot of points. Best of luck on your first project! We (humans Hrolenok, Samudio, and JackGeePTee) look forward to seeing your computational models in action.
Problem You are in charge of directing water through an aqueduct from a source to several bath houses. The aqueduct consists of stations connected by ramps that carry water. The stations are laid out in an m x n grid, in which the source station S is located at position (0,0). From any station located at position (x,y), where 0
Algorithm Abstraction & Design 1 Problem Definition Consider the problem of curating an art exhibition featuring n paintings that must be displayed in a specific sequence determined by the theme of the show; thus, their order cannot be changed. Each painting si, where 1 ≤ i ≤ n, has a base width wi and a height hi. The gallery space is divided into display platforms, each with a fixed maximum width W. The total width of the paintings placed on a single platform cannot exceed W. We have the flexibility to adjust the height of each platform to match the tallest painting placed upon it. The cost of a particular arrangement is the sum of the heights of the tallest paintings on each platform. Your goal is to determine an assignment of the paintings to platforms that minimizes the total cost. Example 1: n = 7, W = 10, hi = [21,19,17,16,11,5,1] wi = [7,1,2,3,5,8,1] Solution 1: Platform1 = [s1…s3]; Platform2 = [s4…s5]; Platform3 = [s6…s7]; cost = 21 + 16 + 5 = 42 Example 2: n = 4, W = 10, hi = [8, 10, 9, 7] wi = [8, 1, 2, 2] Solution 2: Platform1 = [s1]; Platform2 = [s2 …s4]; cost = 8 + 10 = 18 Example 3: n = 7, W = 10, hi = [12, 10, 9, 7, 8, 10, 11] wi = [3, 2, 3, 4, 3, 2, 3] Solution 3: Platform1 = [s1 …s3]; Platform2 = [s4]; Platform3 = [s5 …s7]; cost = 12 + 7 + 11 = 30 ProblemG Given the heights h1,…,hn and the base widths w1,…,wn of n paintings, along with the width W of the display platform, find an arrangement of the paintings on platforms that minimizes the total height. ProblemS1 Given the heights h1,…,hn, where hi ≥ hj ∀i < j, and the base widths w1,…,wn of n paintings, along with the width W of the display platform, find an arrangement of the paintings on platforms that minimizes the total height. (Note: The heights of the paintings form a monotonically non-increasing sequence, as in Example 1.) ProblemS2 Given the heights h1,…,hn, where ∃k such that ∀i < j ≤ k, hi ≥ hj and ∀k ≤ i < j, hi ≤ hj, and the base widths w1,…,wn of n paintings, along with the width W of the display platform, find an arrangement of the paintings on platforms that minimizes the total height. (Note: The heights of the paintings follow a unimodal function with a single local minimum, as in Example 3.) 2 MILESTONE 1 – Greedy Algorithms For the first part of the project, you will design, analyze and implement greedy algorithms to solve the special cases of the problem. You will conduct an experimental study on the performance of your algorithms. You are also required to construct examples showing how an algorithm developed for a special case of the problem might not work for the general version of the problem. 2.1 Design, Analysis, and Implementation Tasks Algorithm1 Design a Θ(n) time greedy algorithm for solving ProblemS1. Analysis1 Prove the correctness of your greedy Algorithm1 for solving ProblemS1. Question1 Give an input example showing that Algorithm1 does not always solve ProblemG. Question2 Give an input example showing that Algorithm1 does not always solve ProblemS2. Program1 Give an implementation of your greedy Algorithm1. Algorithm2 Design a Θ(n) time greedy algorithm for solving ProblemS2. Analysis2 Prove the correctness of your greedy Algorithm2 for solving ProblemS2. Program2 Give an implementation of your greedy Algorithm2. 2.2 Experimental Comparative Study Test your implementations extensively for correctness and performance. For this purpose, you should create randomly generated input files of various sizes. The exact size of the experimental data sets that your program can handle depends on the quality of your implementation. For instance, you might want to choose n = 1000,2000,3000,4000,5000 to create at least five data sets for each experiment. Then, you should conduct and present a performance comparison of the following: For each comparison, generate a two dimensional plot of running time (yaxis) against input size (x-axis). These should be included in your report along with additional comments/observations. Plot1 Plot the running time of Program1 with respect to varying input size (as x-axis). Plot2 Plot the running time of Program2 with respect to varying input size (as x-axis). 2.3 Report Prepare a report that describes design and analysis of your algorithms, presents the results of experimental study, and summarizes your learning experience. Your report should include but not limited to the following sections. • Algorithm Design and Analysis. Give a clear description of your algorithm design and as well as its analysis. You can also include the pseudo code of your algorithms. Make sure to provide the answers to Question1 and Question2 as well. • Experimental Study. Present the results of your experimental study. Include all your plots along with any explanation and comments you wish to provide. • Conclusion. Summarize your learning experience on the first component of the project assignment. For each programming task, comment on the ease of implementation and other potential technical challenges. 2.4 Deliverables The following contents are required for Milestone1 submission: • Implementation: Submit the implementation code on Gradescope. Refer to Section 5 for more details. Make sure to include detailed comments next to each non-trivial block of code. • Report: The report, in PDF format, must be submitted on Canvas. 3 MILESTONE 2 – Dynamic Programming Algorithms For the second part of the project, you will design, analyze and implement dynamic programming algorithms to solve the general cases of the problem. You will conduct an experimental study on the performance of your algorithms. 3.1 Design, Analysis, and Implementation Tasks Algorithm3 Design a Θ(n2n−1) time naive algorithm for solving ProblemG. Analysis3 Give an analysis (correctness & running time) of Algorithm3 for solving ProblemG. Algorithm4 Design either a Θ(n3) time dynamic programming algorithm or a Θ(n2|W|) time dynamic programming algorithm for solving ProblemG. Analysis4 Give an analysis (correctness & running time) of Algorithm4 for solving ProblemG. Algorithm5 Design a Θ(n2) time dynamic programming algorithm for solving ProblemG. Analysis5 Give an analysis (correctness & running time) of Algorithm5 for solving ProblemG. Program3 Give an implementation of Algorithm3. Program4 Give an implementation of Algorithm4. Program5A Give a top-down recursive implementation of Algorithm5 using memoization. Program5B Give an iterative bottom-up implementation of Algorithm5. 3.2 Experimental Comparative Study Test your implementations extensively for correctness and performance. For this purpose, you should create randomly generated input files of various sizes. The exact size of the experimental data sets that your program can handle depends on the quality of your implementation. For instance, you might want to choose n = 1000,2000,3000,4000,5000 to create at least five data sets for each experiment. Then, you should conduct and present a performance comparison of the following: For each comparison, generate a two dimensional plot of running time (yaxis) against input size (x-axis). These should be included in your report along with additional comments/observations. Plot3 Plot the running time of Program3 with respect to varying input size (as x-axis). Plot4 Plot the running time of Program4 with respect to varying input size (as x-axis). Plot5 Plot the running time of Program5A with respect to varying input size (as x-axis). Plot6 Plot the running time of Program5B with respect to varying input size (as x-axis). Plot7 Overlay Plots 3,4,5,6 and contrasting the performance of Programs 3,4,5A,5B. Plot8 Overlay Plots 5,6 and contrasting the performance of Programs 5A, 5B. In addition to testing the running time performance of the algorithms described above, you are asked to conduct experiments to test the quality of the output of Program1 which implements greedy Algorithm1, when it is run on the general case of the problem ProblemG. Note that such solution is not guaranteed to be optimal. Your task is to determine how different it is from the optimal. Make sure to conduct enough experiments with many random data sets. For x-axis, simply use n as the varying input size. On y-axis you can simply plot (hg − ho)/ho, where ho is the optimal height determined by any of Programs 3,4,5A,5B, and hg is the height determined by Program1. Plot9 Plot the output quality comparison (hg − ho)/ho of Program1 and any of Programs 3,4,5A,5B. 3.3 Report Prepare a report that describes design and analysis of your algorithms, presents the results of experimental study, and summarizes your learning experience. Your report should include but not limited to the following sections. • Algorithm Design and Analysis. Give a clear description of your algorithm design and as well as its analysis. Make sure to include the recursive formulation expressing optimal substructure for the dynamic programming algorithms. You can also include the pseudo code of your algorithms. • Experimental Study. Present the results of your experimental study. Include all your plots along with any explanation and comments you wish to provide. • Conclusion. Summarize your learning experience on the first component of the project assignment. For each programming task, comment on the ease of implementation and other potential technical challenges. 3.4 Deliverables The following contents are required for Milestone2 submission: • Implementation: Submit the implementation code on Gradescope. Refer to Section 5 for more details. Make sure to include detailed comments next to each non-trivial block of code. • Report: The report, in PDF format, must be submitted on Canvas. 4 MILESTONE 3 – Video Presentation Prepare a video of length between 5 to 7 minutes, that presents all your results (design, analysis, experiments, and learning experience). Following are the expected components. Summarize your results on algorithm design and analysis. Note that you have already detailed these in your report. Given the time limit for the presentation, it is best to focus on the challenging components. For instance of all the design and analysis tasks, I recommend you spend more time presenting the following: Algorithm2, Analysis2, Algorithm4, Analysis4, Algorithm5, Analysis5. Also, contrast Algorithm4 and Algorithm5, given that both are dynamic programming algorithms solving the same problem but they have different time complexity. [recommended time: upto 2-4 minutes] Comment on your implementations (e.g., whether you used any other resources/libraries) and make a demo of your implementations clearly showing that they work. [recommended time: 2-3 minutes] Summarize your experimental study results, using your plots. [recommended time: 1 minute] In conclusion briefly comment on your learning experience. For group projects, all members must take part in the video presentation. 5 Language/Input/Output Specifications The autograder on Gradescope runs on an Ubuntu 22.04 image. C++ code will be compiled using g++ 11.4.0 with the ‘-std=gnu++17‘ compile flag. Java code will be compiled and evaluated using OpenJDK 17. Python code will be evaluated using Python 3.10. For convenience, you can assume that 1 ≤ n,W < 105, and ∀i 1 ≤ h[i],w[i] < 105. Test cases will be generated to accommodate the required time complexity. Input. Your program will read input from standard input (stdin) in the following order: • Line 1 consists of two integers n and W separated by a single space. • Line 2 consists of n integers (height of n paintings) separated by a single space. • Line 3 consists of n integers (base width of n paintings) separated by a single space. Output. Your program should print to standard output (stdout) in the following order: • Line 1 contains the number of platforms used (denoted as m) • Line 2 contains the optimal total height. • The next m lines should consist of the number of paintings on each platform. 6 Grading Policy For Milestones 1 and 2, grades will be based on the correctness & efficiency of algorithms and the quality of your experimental study and report: • Program 60%. Correct/efficient design and implementation/execution. Also make sure to include comments with your code for clarity. • Report 40%. Quality (clarity, details) of the write up on your design, analysis, programming experience, and experimental study.
Problem You are in charge of directing water through an aqueduct from a source to several bath houses. The aqueduct consists of stations connected by ramps that carry water. The stations are laid out in an m x n grid. From any station located at position (x,y), where 0
Final project COP4533 – Algorithms, Abstraction, and Design Contents 1 Project Description: 2 1.1 Problem Statement – 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Input: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Output: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Constraints: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.4 Example: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Problem Statement – 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Input: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Output: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 Constraints: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.4 Example: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Problem Statement – 3: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.1 Example: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Tasks 4 2.1 Task – 1: Brute Force Algorithm for Problem1 . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Task – 2: Greedy Algorithm for Problem1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Task – 4: Dynamic Programming Algorithm for Problem2 . . . . . . . . . . . . . . . . . . 4 2.4 Task – 5: Dynamic Programming Algorithm for Problem2 . . . . . . . . . . . . . . . . . . 4 2.5 Task – 6: Dynamic Programming Algorithm for Problem3 . . . . . . . . . . . . . . . . . . 4 2.6 Task – 7: Dynamic Programming Algorithm for Problem3 . . . . . . . . . . . . . . . . . . 5 3 Groups 5 4 Milestone 1: Understanding the problems 5 4.1 Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.2 Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.3 Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.4 TODO: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5 Milestone 2: Algorithm Design 7 5.1 TODO: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6 Milestone 3: Algorithm Implementation 7 6.1 TODO: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 7 Presentation 8 1 PROJECT DESCRIPTION: 8 Rubrics 8 8.1 Milestone 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 8.2 Milestone 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 8.3 Milestone 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 9 General Notes 8 1 Project Description: In this final project, you will have the opportunity to design and implement some algorithms to solve variations of Stock buy sell to maximize profit problem. The problem set is divided into different tasks, each with its own unique objectives and requirements. 1.1 Problem Statement – 1: You are given a matrix A of dimensions m × n, where each element represents the predicted prices of m different stocks for n consecutive days. Your task is to determine a single transaction involving the purchase and sale of a single stock that yields the maximum profit. 1.1.1 Input: • A matrix A of dimensions m×n (1 ≤ m,n ≤ 1000), where each element A[i][j] (0 ≤ A[i][j] ≤ 105) represents the predicted price of the i-th stock on the j-th day. Rows represent stocks, columns represent days. 1.1.2 Output: Return a tuple (i, j1, j2, profit) where: • i (1 ≤ i ≤ m) is the index of the chosen stock. • j1 (1 ≤ j1 ≤ n) is the day when you would sell the stock to maximize profit. • j2 (1 ≤ j2 ≤ n) is the day when you would sell the stock to maximize profit. • profit is the maximum profit achievable through this single transaction (sell price minus buy price). 1.1.3 Constraints: 1. You can only perform one transaction, which involves buying and selling a single stock. You can only sell the stock you bought previously. 2. You must buy before selling; in other words, j1 must be less than j2. 3. The prices are non-negative integers and represent the stock’s value at a specific time. 4. You want to maximize profit, so you’re looking for the highest possible difference between the sell price and the buy price. 5. If no profitable transaction is possible, return a tuple (0, 0, 0, 0) to indicate this. 1.1.4 Example: Input: 7 1 5 3 6 2 4 3 7 9 A = 5 8 9 1 2 9 3 14 8 7 Output: (4,2,3,11) Explanation: Choosing the 4th stock (1-based indexing). Buying it in day 2nd day and selling it on the 3rd day (1-based indexing), yields the maximum profit of 11 (sell price 14 minus buy price 3). 1.2 Problem Statement – 2: 1 PROJECT DESCRIPTION: 1.2 Problem Statement – 2: You are given a matrix A of dimensions m × n, where each element represents the predicted prices of m different stocks for n consecutive days. Additionally, you are given an integer k (1 ≤ k ≤ n). Your task is to find a sequence of at most k transactions, each involving the purchase and sale of a single stock, that yields the maximum profit. 1.2.1 Input: • A matrix A of dimensions m × n (1 ≤ m, n ≤ 1000), where each element A[i][j] (0 ≤ A[i][j] ≤ 105) represents the predicted price of the i-th stock on the j-th day. • An integer k (1 ≤ k ≤ n) representing the maximum number of transactions allowed. 1.2.2 Output: Return a sequence of tuples (i, j1, j2) representing the transactions where: • i (1 ≤ i ≤ m) is the index of the chosen stock. • j1 (1 ≤ j1 ≤ n) is the day when you would buy the stock to maximize profit in this transaction. • j2 (1 ≤ j2 ≤ n) is the day when you would sell the stock to maximize profit in this transaction. 1.2.3 Constraints: 1. You can perform at most k transactions, each involving the purchase and sale of a single stock. 2. You must buy before selling; in other words, j1 must be less than j2. 3. The prices are non-negative integers and represent the stock’s value at a specific time. 4. You want to maximize profit, so you’re looking for the highest possible difference between the sell price and the buy price. 5. If no profitable transaction is possible, return an empty sequence. If there are multiples sequences achieving the same optimal profit, return any one of them. 1.2.4 Example: Input: 7 1 5 3 6 2 9 3 7 9 A = 5 8 9 1 6 9 3 4 8 7 k = 3 Output: [(2, 1, 2), (1, 2, 3), (2, 3, 5)] Explanation: Performing at most 3 transactions, selling the 2nd stock on the 2nd day after buying on 1st day, 1st stock selling on the 3rd day buying on 2nd day, 2nd stock selling on 5th day buying on 3rd day yields the maximum profit of 17 (transaction 1: 9 − 2 = 7, transaction 2: 5 − 1 = 4, transaction 3: 9 − 3 = 6). Note: In each transaction tuple (i, j1, j2), the buy day j1 is strictly less than the sell day j2. However, when comparing different transactions, we do not consider them overlapping as along as the actual days involved do not conflict. For example, (1,2) and (2,3) are not considered as overlapping because the sell day of the first is the same as the buy day of the second. Similarly, (2,3) and (3,5) are valid together. But if it is (2,4) and (3,5), then we consider them as overlapping. 1.3 Problem Statement – 3: You are given a matrix A of dimensions m × n, where each element represents the predicted prices of m different stocks for n consecutive days. Additionally, you are given an integer c (1 ≤ c ≤ n − 2). Your task is to find the maximum profit achievable by trading stocks, subject to the restriction that you cannot buy any stock for c days after selling any stock. If you sell a stock on day j1, you are not allowed to buy any stock until day j1 + c + 1 in the next transaction. 3 2 TASKS Input: • A matrix A of dimensions m×n (1 ≤ m,n ≤ 1000), where each element A[i][j] (0 ≤ A[i][j] ≤ 105) represents the predicted price of the i-th stock on the j-th day. • An integer c (1 ≤ c ≤ n − 2) representing the waiting period after selling a stock before buying another. Output: Return a sequence of tuples (i, j1, j2) representing the transactions where: • i (1 ≤ i ≤ m) is the index of the chosen stock. • j1 (1 ≤ j1 ≤ n) is the day when you would buy the stock to maximize profit in this transaction. • j2 (1 ≤ j2 ≤ n) is the day when you would sell the stock to maximize profit in this transaction. 1.3.1 Example: Input: 2 6 A = 1 7 1 9 7 7 8 8 8 4 3 9 9 6 3 1 4 0 c = 2 5 1 4 8 9 0 0 9 5 2 7 8 11 2 1 Output: [(3,1,3),(2,6,7)] Explanation: To achieve the maximum profit, buy 3rd stock on day 1, sell it on day 3. buy 2nd stock on day 6 and sell it on day 7 adhering to 2 days waiting period. 2 Tasks 2.1 Task – 1: Brute Force Algorithm for Problem1 Design a brute force algorithm for solving Problem1 that runs in O(m · n2) time. 2.2 Task – 2: Greedy Algorithm for Problem1 Design a greedy algorithm for solving Problem1 that runs in O(m · n) time. Task – 3: Dynamic Programming Algorithm for Problem1 Design a dynamic programming algorithm for solving Problem1 that runs in O(m · n) time. 2.3 Task – 4: Dynamic Programming Algorithm for Problem2 Design a dynamic programming algorithm for solving Problem2 that runs in O(m · n2k) time. 2.4 Task – 5: Dynamic Programming Algorithm for Problem2 Design a dynamic programming algorithm for solving Problem2 that runs in O(m · n · k) time. 2.5 Task – 6: Dynamic Programming Algorithm for Problem3 Design a dynamic programming algorithm for solving Problem3 that runs in O(m · n2) time.2.6 Task – 7: Dynamic Programming Algorithm for Problem3 Design a dynamic programming algorithm for solving Problem3 that runs in O(m · n) time. 3 Groups 4 Milestone 1: Understanding the problems 4.1 Problem 1 Work out the given numerical example for Problem-1. That is, You are given a matrix A of dimensions m × n, where each element represents the predicted prices of m different stocks f or n consecutive days. Your task is to manually determine the maximum profit achievable through a single transaction, involving the purchase and sale of a single stock. (Refer to problem statement – 1 for output format). Input Matrix A 12 A = 46 14 1 4 8 3 5 13 6 4 3 4 1 8 Steps 1. Begin with the input matrix A as provided. 2. For each stock, calculate the potential profit that could be obtained by selling the stock on eachday after buying it. 3. Identify the day with the highest potential profit for each stock. 4. Determine the stock and day combination that yields the maximum potential profit. Notes • This milestone involves manually applying the basic logic of calculating potential profits and selecting the optimal transaction for a single stock. • The goal is to understand the foundational logic of finding the maximum profit for a single transaction by considering the price differences between different days for a specific stock. 4.2 Problem 2 Work out the given numerical example for Problem-2. That is, You are given a matrix A of dimensions m × n, where each element represents the predicted prices of m different stocks for n consecutive days. Additionally, you are given an integer k (1 ≤ k ≤ n). Your task is to manually find a sequence of at most k transactions, each involving the purchase and sale of a single stock, that yields the maximum profit. (Refer to problem statement – 2 for output format). 4.3 Problem 3 4 MILESTONE 1: UNDERSTANDING THE PROBLEMS Input Matrix A 25 A = 1030 5 Steps 30 15 20 30 45 35 50 35 k = 3 40 25 10 25 50 5 15 45 1. Begin with the input matrix A as provided. 2. Determine the sequence of at-most K non-overlapping transactions. A valid transaction is a buysell of the same stock. Different transactions can have different stocks, but one transaction would deal with only a single stock. 3. Output should be a sequence of at most K transactions in the format of (i,j,l) that yields the maximum potential profit by selling ith stock on lth day that was bought on jth day. Notes • This milestone involves manually applying the basic logic of calculating potential profits and selecting the optimal transaction for a single stock. • The goal is to understand the foundational logic of finding the maximum profit for atmost K nonoverlapping transactions by considering the price differences between different days for a specific stock (in a single transaction). 4.3 Problem 3 Work out the given numerical example for Problem-3. Work out the given test-case for Problem-3 manually. That is, You are given a matrix A of dimensions m × n, where each element represents the predicted prices of m different stocks for n consecutive days. Additionally, you are given an integer c (1 ≤ c ≤ n − 2). Your task is to manually determine the maximum profit achievable under the given trading restrictions, where you cannot buy any stock for c days after selling any stock. If you sell a stock on day i, you are not allowed to buy any stock until day i + c + 1. (Refer to problem statement – 3 for output format). Input Matrix A 7 1 5 3 6 8 9 2 4 3 7 9 1 8 A = 5 8 9 1 2 3 10 9 3 4 8 7 4 1 3 1 5 8 9 6 4 c = 2 Steps 1. Begin with the input matrix A and integer c as provided. 2. For each day j, identify the maximum price to sell the stock l. You can only buy another stock after c + 1 days (i.e., on day l + c + 1 or later) 3. Determine the sequence (i,j,l) that yields the maximum potential profit by selling ith stock on lth day that was bought on jth day. 4.4 TODO: 6 MILESTONE 3: ALGORITHM IMPLEMENTATIONNotes • This milestone involves manually applying the logic of identifying the optimal days to buy and sell stocks based on the given trading restrictions. • The goal is to understand the foundational logic of finding the maximum profit under trading restrictions while considering the waiting period between selling and buying stocks. 4.4 TODO: • Create a private GitHub Repository and add instructional team members as contributors • Coordinate with your team members : communication methods, internal deadlines, responsibilities, meetings, and roles. • Solve together the numerical examples provided • Push into the GitHub repository a pdf document titled: Project – Milestone 1.pdf . The document must contain the following sections: Group members (names, emails and GitHub accounts), Member Roles, Communication method, Project Gantt Chart (including internal deadlines and meetings), GitHub repository link, and solution to the three working examples. • One member of the group must submit the pdf document to Canvas too 5 Milestone 2: Algorithm Design Formulate the problems and design an algorithms. Provide pseudocode for the following tasks: 1. Task – 1 2. Task – 2 3. Task – 3 4. Any two tasks between task – 4, task – 5, task – 6, task – 7. You must assure that all variables and definitions required are provided before the pseudo-code, for each task. 5.1 TODO: • Push into the GitHub repository a pdf document titled: Project – Milestone 2.pdf . The document must contain all sections from Milestone 1, and in addition to it: the programming language to be used in the implementation of the algorithms, all definitions and assumptions necessary to design the algorithm of each task, and the pseucode of each algorithm. • One member of the group must submit the pdf document to Canvas too 6 Milestone 3: Algorithm Implementation 1. For each of the tasks from Milestone 2, implement the algorithm in your preferred programminglanguage (C++ or Python). 2. Provide the code for the algorithm along with comments to explain your implementation.6.1 TODO: 3. Test your implementation with appropriate test cases (you will be in charge of creating these test cases) to ensure it works correctly. Additional Information: • You are encouraged to use suitable data structures, loops, and conditional statements as needed to implement the algorithm effectively. • Be sure to provide comments within your code to explain key steps and logic. • Test your implementation thoroughly with various inputs to ensure correctness. • Document any assumptions or limitations in your code comments. • Provide citations in your code and document containing any source information that you are using in your project 6.1 TODO: • Push into the GitHub repository a pdf document titled: Project – Milestone 3.pdf . The document must contain all sections from Milestone 1, and Milestone 2 and in addition to it description of the implementation of the algorithm, limitations, comparative analysis, trade-off discussion, analysis of the algorithms, lessons learned, limitations of your algorithms. • One member of the group must submit the pdf document in Canvas too 7 Presentation In addition to the algorithm analysis, you are required to create a presentation video that explains the pseudocode for each of the tasks. The video should be concise and should not exceed 10 minutes in total. Instructions for the Pseudocode Presentation: (a) Create one slide per task that was implemented. On each slide, present the pseudocode for the respective task. Note: make sure to provide a detailed explanation of the pseudocode, step by step. (b) Discuss key algorithmic concepts, data structures used, and any critical decisions made during the implementation of the tasks. (c) Make sure your explanations are clear, concise, and easy to follow. (d) Record your presentation as a video, ensuring it does not exceed the 15-minute time limit. (f) Submit the video in a common format such as MP4. (g) One member of the group must submit the video to Canvas 8 Rubrics 8.1 Milestone 1 8.2 Milestone 2 8.3 Milestone 3 9 General Notes • Commit and push your files to the repository frequently. Item Points Observation Github Repository 5 Full points if repository is complete and shared with instructional team Logistics 5 The document contains all the parts mentioned in section 4.4 TODO Problem 1 – correctness 4 The manual calculation is entirely correct and matches the expected result precisely. Problem 2 – correctness 4 The manual calculation is entirely correct and matches the expected result precisely. Problem 3 – correctness 4 The manual calculation is entirely correct and matches the expected result precisely. Problem 1 – Clarity and Explanation 6 The manual calculation is clear and well-explained, making it easy to understand the steps taken to arrive at the result. Problem 2 – Clarity and Explanation 6 The manual calculation is clear and well-explained, making it easy to understand the steps taken to arrive at the result. Problem 3 – Clarity and Explanation 6 The manual calculation is clear and well-explained, making it easy to understand the steps taken to arrive at the result. Total 40 • Make sure the repository is accessible to the instructional team members (syllabus) and contains all the necessary files. • Remember that the goal of this project is not just to obtain correct results, but also to understand and explain the underlying concepts and strategies. Your project will be evaluated based on the following aspects: • Correctness and completeness of algorithm design and implementation. • Accuracy of the comparative analysis and trade-off discussion. • Clarity and quality of project documentation and presentation. • Demonstrated understanding of algorithmic concepts and their application. • Effort. As demonstrated by your commits to the project. This is not only the amount but also the steady work on the project during the semester. This is an individual evaluation. Item Points Observation Github Repository 5 Full points if the repository is complete and shared with instructional team and contains the submission Logistics 5 The document contains all the parts mentioned in section 5.1 TODO Problem 1 – correctness 15 Pseudocode is entirely correct, with no logical errors, accurately represents the algorithm’s logic, is clear and understandable. Problem 2 – correctness 15 Pseudocode is entirely correct, with no logical errors, accurately represents the algorithm’s logic, is clear and understandable. Problem 3 – correctness 15 Pseudocode is entirely correct, with no logical errors, accurately represents the algorithm’s logic, is clear and understandable. Problem 1 – Clarity and Explanation 15 Pseudocode is exceptionally clear, with precise descriptions of each step and logical flow. Problem 2 – Clarity and Explanation 15 Pseudocode is exceptionally clear, with precise descriptions of each step and logical flow. Problem 3 – Clarity and Explanation 15 Pseudocode is exceptionally clear, with precise descriptions of each step and logical flow. Total 100 Item Points Observation Github Repository 10 Repository is complete and shared with instructional team and contains the submission Logistics 40 The document contains all the parts mentioned in section 6.1 TODO Problem 1 – code correctness 25 The code is correct, it solves the given problem statement and passes all hidden test cases without any errors. Problem 2 – correctness 25 The code is correct, it solves the given problem statement and passes all hidden test cases without any errors. Problem 3 – correctness 25 The code is correct, it solves the given problem statement and passes all hidden test cases without any errors. Problem 1 – Readability and Efficiency 25 The code is well-structured, easy to read, and includes thorough comments explaining critical parts. Problem 2 – Readability and Efficiency 25 The code is well-structured, easy to read, and includes thorough comments explaining critical parts. Problem 3 – Readability and Efficiency 25 The code is well-structured, easy to read, and includes thorough comments explaining critical parts. Total 100
Sorting Read all the pages before starting to write your codeIntroduction: For this assignment you have to write a c program that will use Merge sortWhat should you submit? Write all the code in a single file and upload the main.c file Please include the following commented lines in the beginning of your code to declare your authorship of the code:/* COP 3502C Assignment 4 This program is written by: Your Full Name */Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Caution!!!What to do if you need clarification on the problem?How to get help if you are stuck?Problem: Projector Objective Give practice with merge sort in C. Practice with compareTo function strategy to compare objects in C while sorting Practice with floating point comparison strategy in C Story Before starting to read the assignment, you can probably watch the recording posted in the announcement where I have briefly discussed the requirements and some hints. Your movie theater is trying out a new projector. The projection will be in the center of a circular room and will project a movie onto a part of the wall. The screen will project a sector of light at some angle width which comes at some default value, but can be updated based on a setting. The projector can be rotated such that the projection starts at any angle in the room.However, you have several locations that groups of people have decided to stand at in the room. These groups of people are relatively small compared to the distance they are from the projector and can be treated as points with 0 radius. Although the projection won’t be disturbed by our infinitely thin customers, the light emitted from the projector will be harmful to the people in the group.You want to answer 2 main questions. 1. What is the largest possible angle of projection that can be used such that no group will be standing in the projection, thus will not harm anyone? 2. Find all the ways you can project this largest angle and show the list of pairs of groups that will be closest to the edge of those projections. It means, if there are multiple ways to get that largest angle, you need to list all the pairs of groups that are closest to the projection edge. Problem Given the locations and number of people in the groups, determine the largest angle that can be used such that no one is in the projection. Additionally, find all the ways you can project this largest angle and show the list of pairs of groups will be closest to the edge of the projection.Input (no file i/o. Only standard input) Input starts with a line containing 2 integers, N and A, (1 ≤ N ≤ 500,000; 1 ≤ A ≤ 359) representing the number of groups standing in the room and the angle in degrees at which the screen projector initially projects (However, we will change this default setting).The following N lines will each contain 3 space separated integers, x, y, and s, (0 ≤ |x|, |y| ≤ 1,000,000; 1 ≤ s ≤ 1,000), representing x and y coordinates respectively of the location of a group and the number of people in that given group. Assume that the projector will be located at location (0, 0). Also, you can consider they are entered in a sequence of group numbers starting from 0 to ending at N-1. It means the first x, y, and s represent the data for group 0, the second one is group 1 and so on. It is also guaranteed that that the position of multiple groups will not be exactly in the same angle in reference to the x-axis. For example, if a group’s position is (1,1), then there will not be a group at position (2,2) as both (1,1) and (2,2) are at 45 degree angle from the x-axis.Note since the customers are so small multiple customers could stand at the same location. Output The output should consist of two items: The first line will contain a floating-point value that specifies the maximum angle in degrees that can be used such that no person will be in the projection rounded to 4 digits after the decimal. Assuming, there are P different ways that maximum angle can be projected, print a list of P pairs, one per line containing the group numbers that will be closest to the projection edge. While printing a pair, the first group number must be smaller than the second group number. Also, the list of pairs must be printed as a sorted list. If multiple pairs starts with same group number, then it must be sorted based on the second group number in the pair. Sample Input Sample Output 4 91 0 5 3 10 0 5 -4 0 12 0 -3 4 Max projection degree without harming 90.0000 Closest possible group pairs in order: 0 1 0 2 1 3 2 3 3 181 1 1 8 -2 1 5 2 10 10 Max projection degree without harming 251.5651 Closest possible group pairs in order: 0 1Explanation Case 1 In the first test case there are 4 groups. The red colored numbers represent the group numbers.You can use an angle slightly less than 90 degrees to project with no group in the projection. See the example image where these 90 degrees is achieved between group 0 and 1. You can get this 90 degrees in 4 different ways. Between group 0 and 2, between 2 and 3, and between 1 and 3. Also, if you observe the output, it is in ordered based on the group number of the pair. If there is a tie in the first number of the pair, it is sorted base on the second number. Example: 0 1 0 2 (as the first item is zero for both of them, it is ordered by the second item for those cases)The angle can be quite large without projecting on anybody. We can get this angle keeping group pair 0 and 1 close the edge. Some implementation restrictions and hints: – You must create two structs, one for group and one for Result. The group struct can contain group size, angle (in radian), and the group number. The result struct contains a pair (two int firstGroup and secondGroup), and angle (in degree). You can modify the content of the struct. But keeping the mentioned structure fields will help you. – You must use dynamic memory allocation for both all the arrays. As the size of the result array is not known initially, you can allocate it based on the number of groups and use tracker to track how many of them are used. – Convert each position of a group into radian angle. Explore the tan2 function of math.h library to calculate this. If you need to review what is radian, maybe watch this YouTube video: https://www.youtube.com/watch?v=Aqm8v0fJDzM – After sorting the groups based on angle, you can now iterate through them to find the max angle as part of the answer. – Based on the answer, you can now build the result array with all the pair based on the sorted groups and their angle. Make sure the group 1 and group 2 of a result struct value is ordered. o As you will store only the pairs that has an angle equal to the max angle you found earlier, there is possibility of error in equality comparison as they are floating point numbers o For example. See the issue in the following piece of code: double d1 = 13+0.2+0.2+0.1; /* 13.5 ? */ double d2 = 14-0.2-0.2-0.1; /* 13.5 ? */ if(d1==d2) { printf(“They’re the same %lf %lf ”,d1,d2); } else { printf(“They’re not the same %lf %lf ”,d1,d2); } Output: They’re not the same 13.500000 13.500000 o To deal with this problem, we have to use a threshold (epsilon). If the difference of two floating point numbers are within the threshold, we consider them as equal. For example, if a and b are two floating point numbers, we can consider that they are same if the absolute value of their difference is less then epsilon. For this assignment use 0.0001 as the value for epsilon. ▪ fabs(a-b) < epsilon o write a function doubleCompare(double d1, double d2, double eps) that returns 1 if d1 and d2 are same based on the epsilon as discussed above. Otherwise, it should return 0. You must use this function whenever you need to compare two double type of data in your assignment for checking whether they are same or not. o As during this sorting process, you will need to compare two results based the firstGroup and secondGroup property of the result struct, you must implement and use the following compareTo function. o You must write a function compareTo which takes in two pointers, ptrPt1 and ptrPt2, to Result structs and returns a negative integer if the Result pointed by ptrPt1 is smaller than the Result pointed by ptrPt2. Otherwise, it should return a positive number indicating the Result pointed by ptrPt1 is greater than the Result pointed by ptrPt2. As part of this comparison, you should compare the firstGroup property between them fist and if there is a tie, you should compare the secondGroup to make the decision. If both values are exactly same, you should return 0. – You must free all the memory properly to receive full credit – The code must compile and work on codegrade platform – Also, make sure to test your code with more test cases to make sure your code will pass other test cases as well. Tentative Rubric (Subject to change) ● There is no point for well structured, commented and well indented code. There will be a deduction of 10% points if the code is not well indented and 5% for not commenting important blocks.● There is no grade for just writing the required functions and structs. However, there will be 20% penalty for not writing and using CompareTo() function, 10% penalty for not writing and using doubleCompare()function, ● Reading data and loading them into group struct array properly with proper angle calculation: 10 pts ● Sorting the groups based on angle properly using merge sort: 10 pts ● Comparing adjacent sorted groups to find the max angle properly: 10 pts ● Making the Results array properly with the pair and angles: 10 pts ● Soring the Results using merge sort properly: 10 pts ● Programs will be tested on 10 cases ○ 5 points eachSome Steps (if needed) to check your output AUTOMATICALLY in a command line in repl.it or other compiler: You can run the following commands to check whether your output is exactly matching with the sample output or not. Step1: Copy the sample output to sample_out.txt file and move it to the server Step2: compile your code using typical gcc and other commands.# gcc main.c leak_detector_c.c -Wno-unused-result -lmStep3: Execute your code and pass the sample input file as a input and generate the output into another file with the following command $ ./a.out < sample_in.txt > out.txtStep4: Run the following command to compare your out.txt file with the sample output file$cmp out.txt sample_out.txtThe command will not produce any output if the files contain exactly same data. Otherwise, it will tell you the first mismatched byte with the line number.Step4(Alternative): Run the following command to compare your out.txt file with the sample output file$diff -y out.txt sample_out.txtThe command will not produce any output if the files contain exactly same data. Otherwise, it will tell you the all the mismatches with more details compared to cmp command. # diff -c myout1.txt sample_out1.txt //this command will show ! symbol to the unmatched lines.
Read all the pages before starting to write your codeDeliverable: Write all the code in a single main.c file and upload it to codegrade.Please include the following commented lines in the beginning of your code to declare your authorship of the code: /* COP 3502C Assignment 6 This program is written by: Your Full Name */Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Caution!!! What to do if you need clarification on the problem? I will also create a discussion thread in webcourses, and I highly encourage you to ask your question in the discussion board. Maybe many students might have same question as you. Also, other students can reply, and you might get your answer faster. How to get help if you are stuck?Theater Inventory Objective Practice implementing a hash table via separate chaining hashing.Background StoryFor the purposes of this problem, assume that the theater starts with $100,000 to help buy supplies. Over the course of a simulation, the theater can buy supplies, sell products and update the price it sells a particular item. After each update, the theater wants a log of the change to inventory. At the very end of the simulation, the theater would like to know how much money it has. In addition, it would like to have some metrics about the performance of the program.Since the theater knows you are learning about hash tables in class, they would like for you to implement this functionality via a hash table using separate chaining hashing.Problem Write a program that reads in input corresponding to various changes and queries to the theater’s inventory and prints out corresponding messages for input commands 1 and 2. Here is an informal list of each of the possible commands in the input:(1) Buy supplies from a supplier. (2) Sells a quantity of an item to a customer. (3) Update the sale price of an item.For each command, we define the complexity of the command to be as follows:If the desired item is already in the appropriate linked list, then the complexity of the command is equal to k, where the item is stored in the kth node of the linked list (using 1-based counting).If the desired item is NOT in the appropriate linked list (meaning that we must create a new node for buying supplies), then the complexity of the command is equal to the length of the linked list plus 1. (This is also the length of the resulting linked list after inserting the new item.)Your program will compute the sum of complexities of each of the commands, in addition to computing the total amount of cash the theater has after all of the commands are executed.Input The first line of input contains a single positive integer: n (n ≤ 300,000), the number of commands to process.The next n lines will each contain a single command.Here is the format of each of the possible commands:Command 1 buy will be a lowercase alphabetic string with no more than 24 characters, indicating the item being purchased from the supplier. will be a positive integer indicating how many of the item are being purchased. will be a positive integer (in dollars), representing the total purchase price.Command 2 sell will be a lowercase alphabetic string with no more than 24 characters, indicating the item being sold to a customer. will be a positive integer less than or equal to 1000, indicating how many of the item are being sold.Note: if the stock of the item in question is less than the quantity requested, then just sell all of the available quantity of that item. It’s guaranteed that item will be in the inventory.Command 3 change_price will be a lowercase alphabetic string with no more than 24 characters, indicating a valid item in the inventory. will be a positive integer (in dollars), representing the updated price at which the item (single copy) will be sold. It’s guaranteed that item will be in the inventory.It is guaranteed that through all of the commands, the theater will never get below $0 and that the total amount of cash the theater has will never exceed the maximum value that can be stored in an integer variable. Same goes for every individual quantity of any item. Also, each item will have a well-defined price before it’s sold to a customer.Output For each input command of type 1 and 2, output a single line as described below:Commands 1 and 2 Print out a single line with the format: where is the name of the item bought/sold, is the number of that item left in inventory AFTER the transaction, and is the total amount of money left after the transaction.After all of the transactions have completed, print both the total cash on hand at the end of the simulation on a line by itself, followed by the total complexity of all of the operations executed as previously defined, on a line by itself.Sample Input Sample Output 10 buy popcorn 1000 3000 buy soda 2000 1000 change_price popcorn 6 change_price soda 5 sell popcorn 50 sell soda 100 change_price popcorn 8 sell popcorn 90 sell soda 1899 buy soda 10 3popcorn 1000 97000 soda 2000 96000 popcorn 950 96300 soda 1900 96800 popcorn 860 97520 soda 1 107015 soda 11 107012 107012 10Hash Function to Use Please use the following hash function: int hashfunction(char* word, int size) { int len = strlen(word); int res = 0; for (int i=0; i out.txtStep4: Run the following command to compare your out.txt file with the sample output file$cmp out.txt sample_out.txtThe command will not produce any output if the files contain exactly same data. Otherwise, it will tell you the first mismatched byte with the line number.Step4(Alternative): Run the following command to compare your out.txt file with the sample output file$diff -y out.txt sample_out.txtThe command will not produce any output if the files contain exactly same data. Otherwise, it will tell you the all the mismatches with more details compared to cmp command. # diff -c myout1.txt sample_out1.txt //this command will show ! symbol to the unmatched lines.
Recursion Read all the pages before starting to write your codePlease include the following comments at the beginning of your code to declare your authorship of the code: /* COP 3502C Assignment 3 This program is written by: Your Full Name */ Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Caution!!! What to do if you need clarification on the problem? How to get help if you are stuck?PA3: Where to Sit?Objective Give practice with recursion. Give practice with functions in C. Give practice with creating a design for a program without a given list of functions or structs.Background Story You and your friends are planning to get together to attend a movie! However, there are a few restrictions on where everyone can sit:• Some people don’t want to sit next to each other. • Everyone should have access to popcorn! (This means that for each person, either they bought popcorn, or the person directly to their left or the person directly to their right did.)For example, imagine that there are five people who want to attend the movie: Alia, Belinda, Carlos, Danica and Edward, where only Alia and Edward buy popcorn. In addition, Alia and Carlos can’t sit next to each other and Belinda and Edward can’t sit next to each other. Given these restrictions, they can sit in a single row in 10 possible orders.Alia Belinda Carlos Edward Danica Alia Belinda Danica Edward Carlos Belinda Alia Danica Carlos Edward Belinda Alia Danica Edward Carlos Carlos Edward Danica Alia Belinda Carlos Edward Danica Belinda Alia Danica Alia Belinda Carlos Edward Danica Edward Carlos Belinda Alia Edward Carlos Belinda Alia Danica Edward Carlos Danica Alia BelindaProblem Write two related programs where, given the list of people who are going to the movies together, the pairs of people who can’t sit next to each other, and the list of people who are buying popcorn, determines the two following things (Note that these programs will not exchange any data between them. They are just independent code and run independently. Both of them will receive same inputs)):(1) Program 1 – the number of different orderings (permutations) of the movie attendees that satisfy all the restrictions.(2) Program 2 – the first ordering (in lexicographical order) of the movie attendees that satisfy all the restrictions.Input The first line of input contains two positive integers: n (3 ≤ n ≤ 10), the number of people attending the movie, and p (0 ≤ p ≤ n), the number of pairs of people who do not want to sit next to each other.The next n lines will contain the information about each of the people attending the movie, with one person described per line. These lines will describe the people in alphabetical order. Each of these lines will have the following format:NAME 0/1Each name will be an uppercase alphabetic string with no more than 19 characters. If the number 0 is on the line, this indicates that that person does not have popcorn. If the number 1 is on the line, this indicates that that person does have popcorn.The following p lines will each contain a pair of names, indicating two people who do not want to sit next to each other. It is guaranteed that each of the 2p names appearing in this section will be one of the n names listed previously as the movie attendees. Secondly, it’s guaranteed that the two names on a single line will be distinct.Output (for Program 1) On a single line, simply output the total number of valid orderings of the people attending the movie sitting together in a single row, from left to right. It is guaranteed that the input data will be such that this value will be a positive integer.Output (for Program 2) Output, with one name per line, the first lexicographical valid ordering of the people attending the moving sitting together in a single row, from left to right. In lexicographical ordering, all lists starting with name1 will come before all lists starting with name2 if name1 comes before name2 alphabetically. Specifically, given two lists, to determine which one comes first lexicographically, find the first corresponding name on both lists that don’t match. Which ever name comes first alphabetically, is the list that comes first in lexicographical order. (Hint: since the given names are already in alphabetical order, the permutation algorithm shown in class will naturally evaluate the permutations in lexicographical order. Thus, to solve this program, the first valid solution found while running the algorithm will be the correct answer.)Sample Input Sample Output 1 Sample Output 2 5 2 ALIA 1 BELINDA 0 CARLOS 0 DANICA 0 EDWARD 1 ALIA CARLOS BELINDA EDWARD 10 ALIA BELINDA CARLOS EDWARD DANICA 8 3 ALEX 1 ELLIE 1 FRANKLYN 0 JAMELLE 0 MARTY 1 PRI 1 SAMANTHA 1 WES 0 ALEX WES ELLIE MARTY ELLIE WES 10248 ALEX ELLIE FRANKLYN JAMELLE MARTY PRI SAMANTHA WES 6 5 ANEESHA 0 ARTHUR 0 JACQUELINE 1 MATTHEW 1 MEGAN 0 ROBINSON 0 ROBINSON ARTHUR MATTHEW MEGAN MATTHEW ARTHUR ROBINSON MEGAN MEGAN ANEESHA 2 MEGAN JACQUELINE ARTHUR ANEESHA MATTHEW ROBINSON Sample Explanation In each of the three cases, we can verify that the outputted list is valid. (In the first sample, Alia and Edward have popcorn and are in seats 1 and 4. Everyone else is adjacent to one of these two seats. In addition both Alia and Carlos are separated and Belinda and Edward are separated.)In the second sample case, many orderings are possible simply because most of the attendees have popcorn and there are limited pairs of attendees who can’t sit next to each other.In the last sample, popcorn must be in seats 2 and 5. The five pairs of constraints reduces the possibilities to what is listed and its reverse ordering. Implementation Requirements/Run Time Requirements1. No dynamically allocated memory is necessary. All the memory requirements are relatively small.2. The permutation algorithm from class must be used (The used helper array approach). The run time of each program should be roughly O(n x n!). (n! for each permutation and n for evaluating if a permutation is a valid arrangement of the movie attendees.)4. Your code must compile and execute on the Codegrade system.Deliverables1. Please submit a source file, main1.c for your solution to problem A (where the output is a single number).2. Please submit a source file, main2.c, via Webcourses, for your solution to problem B (where the output is a list of names).Some more Hints: – Use the permutation code discussed in the class that uses the used helper array (not the swapping one) [Check the permutation pdf] – Probably, write 3 more functions one for checking popcorn matters, one for order of seating without conflict, and one that will get status from both of these functions and decide if a given permutation is valid or not –
Dynamic Memory Allocation Read all the pages before starting to write your code Overview Your solution should follow a set of requirements to get credit. What should you submit? Write all the code in a single file main.c file and submit it on codegrade. Please include the following commented lines in the beginning of your code to declare your authorship of the code: /* COP 3502C Assignment 1 This program is written by: Your Full Name */Caution!!! What to do if you need clarification on the problem? How to get help if you are stuck? Objective Give practice with structs and dynamic memory in C. Give practice with functions in C. Give practice following a design specification with structs and function prototype requirements.Background Story The demand for movies is higher than ever, and you are going to use this to your advantage to make some decent cash. You need your theater to stand out from its competitors, so you are going to introduce your Unacceptably Luminescent Tech Igniting Many Airplanes Though Eco-friendly (ULTIMATE) projector. The projector in question can be seen for miles, and it works in the sunlight too. You are going to set up a large theater that can fit many people. For now, you need some software that can track who is in what seat efficiently. It seems the software you got from buying out a theater could only handle up to 400-seat theaters. You have much larger ambitions.Problem Description Write a program that can allow for people to buy consecutive seats in a row (if available) and look up who owns the seat at a particular spot in a row. You should assume that the theater starts with every seat available for purchase.Input The input format consists of a sequence of actions and requests, specified in the order in which they occur. Instead of having a fixed number of lines, the input will be sentinel driven; this means that a special word on a line by itself will specify that there is no more input to process. Each line of input will be in one of the following formats:● BUY ○ This means the user with the given will try to purchase the seats in the given . They want the seats with numbers ranging from to inclusive. ○ You are guaranteed that will be at most . ○ If any other user owns at least one seat in this range, the purchase should NOT go through. ● LOOKUP ○ This means that we need to determine which user, if any, purchased the seat with the number in the given . ● EXIT ○ This should terminate the program and clean up any memory., , , and will all be positive integers in the range of 1 to 100,000, inclusive. The will be an alphabetic single word string of at most 50 characters (use scanf with %s). Finally, there will never be more than 100 successful BUY operations executed on a single row. Output For each BUY input, output a single line containing the word “SUCCESS” if the purchase was successful, and “FAILURE” otherwise. For each LOOKUP input, output a single line containing solely the name of the user that owns the seat, if the seat is owned and “None”, if the seat is unowned. Sample Input Sample Output BUY 1 5 10 ALICE BUY 1 7 7 Bob BUY 2 5 10 Carol LOOKUP 1 7 LOOKUP 1 10 LOOKUP 1 1 BUY 1 1 4 David LOOKUP 1 1 BUY 1 2 5 Eric BUY 10 1000 1000 SAM EXIT SUCCESS FAILURE SUCCESS ALICE ALICE None SUCCESS David FAILURE SUCCESS LOOKUP 1 1 LOOKUP 1 2 BUY 3 49998 50003 Guha BUY 1 50000 50000 Meade BUY 5 49999 50001 Ahmed LOOKUP 1 1 LOOKUP 1 49999 LOOKUP 50000 1 LOOKUP 3 50000 EXIT None None SUCCESS SUCCESS SUCCESS None None None Guha Sample Explanation In the first sample, ALICE’s buy is successful but Bob’s isn’t because he tries to buy seat 7 in row 1, which ALICE already has bought. Carol’s buy is also successful in row 2. ALICE does have seats 7 and 10 on the first row (because she bought seats 5 through 10 on that row), but does not have seat one on row 1. David follows this up by buying all the seats with lower numbers on row 1 next to Alice’s block of seats. Right after this buy, David has seat 1 in row 1. Eric can’t buy the seats he wants in row 1 because they are already bought by both David and ALICE. Finally, SAM can buy seats in row 10 because they are all open to buy.Required Structs and Function Prototypes Here are three #defines for important constants to use: #define INITSIZE 10 #define MAXLEN 50 #define MAXROWS 100000The first represents the initial size of any row (in terms of number of orders). The second represents the maximum length of a name for an order. The third represents the maximum number of rows in the theater.For safety reasons (or if you want to use 1-based indexing), feel free to add 1 to the last two.The following struct definition should be used for an order:typedef struct order { int s_seat; int e_seat; char* name; } order;The reason the row isn’t stored in the order is that each row number will implicitly be equal to the index in the array storing the rows for the movie theater.A second required struct will manage a single row. A vast majority of the logic of the assignment will be done in the functions associated with this struct:typedef struct theaterrow { order** list_orders; int max_size; int cur_size; } theaterrow; Here are functions you are required to write. What is given is both the function signature and a description of what the function does:// Returns a pointer to a dynamically allocated order storing the given // start row, end row, and the name this_name. Note: strcpy should be // used to copy the contents into the struct after its name field is // dynamically allocated. order* make_order(int start, int end, char* this_name);// This function will allocate the memory for one theaterrow, including // allocating its array of orders to a default maximum size of 10, and // setting its current size to 0. theaterrow* make_empty_row();// Assuming that order1 and order2 point to orders on the same row, this // function returns 1 if the orders conflict, meaning that they share // at least 1 seat in common, and returns 0 otherwise. int conflict(order* order1, order* order2)// Returns 1 if the order pointed to by this_order can be added to the // row pointed to by this_row. Namely, 1 is returned if and only if // this_order does NOT have any seats in it that are part of any order // already on this_row. int can_add_order(theaterrow* this_row, order* this_order);// This function tries to add this_order to this_row. If successful, // the order is added and 1 is returned. Otherwise, 0 is returned and // no change is made to this_row. If the memory for this_row is full, // this function will double the maximum # of orders allocated for the // row (via realloc), before adding this_order, and adjust max_size and // cur_size of this_row. void add_order(theaterrow* this_row, order* this_order);// If seat_num seat number in row number row is occupied, return a // pointer to the owner’s name. Otherwise, return NULL. char* get_owner(theaterrow** theater, int row, int seat_num);// If seat_num in the row pointed to by this_row is occupied, return a // pointer to the string storing the owner’s name. If no one is sitting // in this seat, return NULL. char* get_row_owner(theaterrow* this_row, int seat_num);// This function returns 1 if the seat number seat_no is contained in // the range of seats pointed to by myorder, and returns 0 otherwise. int contains(order* myorder, int seat_no);// Frees all memory associated with this_order. void free_order(order* this_order);// Frees all memory associated with this_row. void free_row(theaterrow* this_row); Finally, in the main function, the whole theater will be declared as follows (you can choose any variable name you want): theaterrow** amc_= calloc(MAXROWS+1, sizeof(theaterrow*)); This allocates an array, where each element in the array is a pointer to a theater row. The memory associated with this variable should be freed, in main, at the very end of the program. Implementation Requirements/Run Time Requirements 2. For full credit, the functions can_add_order, add_order, get_owner, and get_row_owner, should all run in linear time in the length of the relevant row upon which they operate. (Here linear time means, your code should not try to access all the items of the array multiple times while processing one of these functions.). 3. Your code must compile and execute on CodeGrade. 4. Please do not use memory leak detector header file and atexit line in your code like shown in Lab2 as this assignment is dealing with large number of malloc and using the mentioned leak detector will make the execution of your code extremely slow. Instead, use valgrind command to check whether you have any memory leak in your code or not and where is it happening. See the page on the dynamic memory allocation module about valgrind. Deliverables Please submit a single source file, main.c, via CodeGrade. Rubric (subject to change): According to the Syllabus, the code will be compiled and tested in Codegrade Platform for grading. If your code does not compile in Codegrade, we conclude that your code is not compiling and it will be graded accordingly. We will apply a set of test cases to check whether your code can produce the expected output or not. Failing each test case will reduce some grade based on the rubric given bellow. If you hardcode the output, you will get -200% for the assignment. 2. If you modify or do not use the required structure, you will get 0 3. If you use file i/o instead of using scanf, then you will get 0 4. Not using dynamic memory allocation for storing data will receive 0 5. There is no grade for a well indented and well commented code. But a bad indented code will receive 20% penalty. Not putting comment in some important block of code -10% 6. Implementing required functions and other requirements: 30% a. 5 pts for using the required structs (2.5+2.5) b. Implementing and using the 10 required functions: 25 pts (2.5 each) 7. Freeing up memory properly with zero memory leak (if all the required malloc implemented): (20%) 8. Passing test cases: 50% 9. Note that we will use more test cases while grading and the test cases will follow the assignment input and output specifications. Passing sample test cases cannot guarantee that your code will pass grading test cases as well. You should test your code thoroughly with your own test cases to make sure your code is solving the problem accurately. Some Steps (if needed) to check your output AUTOMATICALLY in a command line in repl.it or other compiler with terminal option: You can run the following commands to check whether your output is exactly matching with the sample output or not. Step1: Copy the sample output to sample_out.txt file and move it to the server Step2: compile your code using typical gcc and other commands.# gcc main.c -Wno-unused-result -lm (use -g as well if you plan to use valgrind and want to see the line numbers with the memory leak)Step3: Execute your code and pass the sample input file as a input and generate the output into another file with the following command $ ./a.out < sample_in.txt > out.txtStep4: Run the following command to compare your out.txt file with the sample output file$cmp out.txt sample_out.txtThe command will not produce any output if the files contain exactly same data. Otherwise, it will tell you the first mismatched byte with the line number.Step4(Alternative): Run the following command to compare your out.txt file with the sample output file$diff -y out.txt sample_out.txtThe command will not produce any output if the files contain exactly same data. Otherwise, it will tell you the all the mismatches with more details compared to cmp command. # diff -c myout1.txt sample_out1.txt //this command will show ! symbol to the unmatched lines. Some hints:– The core concepts of the example of dynamically allocating array of structure pointer, dynamically allocating array of strings, and the Lab2 code would be very useful before starting this assignment. You should really watch these specific recording before starting this assignment. – Start the assignment as soon as possible. – Break it down by drawing and designing, – At first see whether you can read all the inputs properly – Then gradually implement functions one by one and test your code gradually. – Do not wait till the end to test your code. Good Luck!
Queues and Linked List Read all the pages before starting to write your code Overview Your solution should follow a set of requirements to get credit. What should you submit? Write all the code in a single file main.c file and submit it on codegrade. Please include the following commented lines in the beginning of your code to declare your authorship of the code: /* COP 3502C Assignment 1 This program is written by: Your Full Name */Caution!!! What to do if you need clarification on the problem? How to get help if you are stuck?Movie Ticketing Queue (Queues)Objective Give practice implementing a queue via a linked list. Give practice designing a functioning program without all function prototypes being given. Give practice following and implementing rules in a simulation. Background StoryUpon arrival, a customer enters the name (a single string with max length 50 with all upper case letters) and number of tickets nt (0< nt ≤500) in the kiosk. The time of arrival t (0 ≤ t ≤ 109) is automatically recorded and is unique for each customer. After receiving this data, the system extracts the first letter of the name and gets its position p (0 ≤ p < 26) in the alphabet. For example, if the name is ADAM, then p for ADAM is 0. (A = 0, B = 1, …, Z = 25) Then the system automatically assigns a queue number q based on the following strategy: 1. The queue number q of a customer is p%13, if p%13≠0Processing the customers For the purposes of this problem, we assume that before the employees start processing customers, it is known in advance which of the queues will be non-empty at some point in time. Let the number of queues that receive at least 1 customer at some point in time equal k.The k queues will be split amongst the b booths as follows: Each booth will receive customers from at least ⌊⌋ queues, where ⌊⌋, represents the greatest integer less than or equal to x. (This is the technical way to define integer division for positive integers, mathematically. It’s called the floor function.) Let’s consider a couple examples. Let the non-empty queues be 1, 3, 4, 8, 9 and 12 and let there be 4 booths. Thus, for this example, all customers from queues 1 and 3 will go to booth 1, all customers from queues 4 and 8 will go to booth 2, all customers from queue 9 will go to booth 3 and all customers from queue 12 will go to booth 4. Booth 1: Queues 2, 3, 4, 6 Booth 2: Queues 7, 8, 9 Booth 3: Queues 10, 11, 12 The booths start processing customers at time t = 0. As soon as the first customer arrives at a booth, the employee at that booth starts processing her order. The processing time (in seconds) of a customer is calculated by 30 + number of tickets * 5. For example, if a customer buys 8 tickets, then it would take 30 + 8*5 = 70 seconds to process her transaction.The Problem Write a program that will reads in information about customers: customer name, number of tickets and time of arrival, and uses this information to determine which booth each customer will buy tickets from, and at what time they will complete their transaction.Input The first line will contain 2 positive integers, n (n ≤ 500,000), the number of customers purchasing tickets and b (b ≤ 12), the number booths operating on that day.The following n lines will have information about each customer. These n lines will be sorted from earliest arrival time to latest arrival time. Each of these lines will start with the name of the customer, a single string of 1 to 50 uppercase letters, followed by a positive integer, nt (0< nt ≤500), representing the number of tickets the customer is buying. The row ends with another unique positive int t (t ≤ 109), representing the time, in seconds, from the beginning of the simulation that the customer steps into a line. It is guaranteed that all of the check in times are unique and that all of the customer names are unique as well. These pieces of information will be separated by white space on the line. (Please just use scanf to read in the input!) The Output For each booth and for each customer served by the booth print the checkout time in the order that they get checked out from that booth.For each booth, print a single line with the following format:Booth Ywhere Y represents the booth number, starting with 1.For each customer who bought tickets at that booth, output a single line with the following format:CUSTOMER from line X checks out at time T.where CUSTOMER is the name of the customer checking out, X is the queue they came from before arriving at the booth, and T is the number of seconds AFTER the start of the simulation, that they complete checking out. (Thus, this time is the time they get called by the booth, plus the time it takes them to process.)After each booth, output a blank line.Sample Input 17 3 TANVIR 10 2 ARUP 8 4 TRAVIS 40 5 LILY 5 10 XIE 60 15 GUSTAVO 55 16 JOSE 20 23 DANIEL 20 27 VENU 24 28 ANEESHA 70 29 ANSH 6 35 GUHA 40 36 MEADE 60 38 MASON 12 40 NELLY 10 150 SHARON 5 5000 LEAVENS 2 9000Sample Output Booth 1 TANVIR from line 6 checks out at time 82. ARUP from line 6 checks out at time 152. TRAVIS from line 6 checks out at time 382. GUSTAVO from line 6 checks out at time 687. DANIEL from line 3 checks out at time 817. ANEESHA from line 3 checks out at time 1197. GUHA from line 6 checks out at time 1427. SHARON from line 5 checks out at time 5055.Booth 2 XIE from line 10 checks out at time 345. JOSE from line 9 checks out at time 475. VENU from line 8 checks out at time 625. ANSH from line 8 checks out at time 685. NELLY from line 9 checks out at time 765.Booth 3 LILY from line 11 checks out at time 65. MEADE from line 12 checks out at time 395. MASON from line 12 checks out at time 485. LEAVENS from line 11 checks out at time 9040.Sample Explanation There are 17 customers and 3 booths open.For Arup, the relevant calculation is 0%13 = 0. This means he gets placed in the queue which has seen the fewest customers (but has seen at least one), which is queue 6.1 2 3 4 5 6 7 8 9 10 11 12DANIEL TANVIR VENU JOSE XIE LILYARUPTRAVIS GUSTAVO1 2 3 4 5 6 7 8 9 10 11 12 DANIEL SHARON TANVIR VENU JOSE XIE LILY MEADE ANEESHAARUP ANSH NELLY LEAVENS MASONTRAVIS GUSTAVO GUHAThere are 8 queues (3, 5, 6, 8, 9, 10, 11, 12) to split amongst 3 booths. The assignment of queues to booths is as follows:Booth 1: Queues 3, 5, 6 Booth 2: Queues 8, 9, 10 Booth 3: Queues 11, 12A tabular format of the numbers is shown below. The booth meeting time of a customer depends on the previous check out time and arrival time. Then the customer’s check out time is calculated based on the formula mentioned above: Name No. of tickets Arrival time Calculated TANVIR 10 2 6 6 b1 2 82 ARUP 8 4 0 6 b1 82 152 TRAVIS 40 5 6 6 b1 152 382 LILY 5 10 11 11 b3 10 65 XIE 60 15 10 10 b2 15 345 GUSTAVO 55 16 6 6 b1 382 687 JOSE 20 23 9 9 b2 345 475 DANIEL 20 27 3 3 b1 687 817 VENU 24 28 8 8 b2 475 625 ANEESHA 70 29 0 3 b1 817 1197 ANSH 6 35 0 8 b2 625 685 GUHA 40 36 6 6 b1 1197 1427 MEADE 60 38 12 12 b3 65 395 MASON 12 40 12 12 b3 395 485 NELLY 10 150 0 9 b2 685 765 SHARON 5 5000 5 5 b1 5000 5055 LEAVENS 2 9000 11 11 b3 9000 9040Implementation Restrictions2. You must create a node struct for a linked list of customers. This struct should have a pointer to a customer struct, and a pointer to a node struct.3. You must create a struct to store a queue of customers. This struct should have two pointers – one to the front of the queue and one to the back, AND an integer field to store the size of the queue.4. For all the above structs, feel free to add more fields if necessary.5. There are several different ways to simulate the process described, but in some way shape or form, you should use the queue struct and the associated functions in the simulation.6. You must dynamically allocate memory as appropriate for linked lists.7. Your queue must support the following operations and you must use them appropriately in your code. Each of these operations should run in O(1) time, meaning you should not need to traverse a linked list to do an operation mentioned below. : a. Enqueue b. Dequeue c. Peek: Return the front of the queue WITHOUT dequeuing. d. Empty (returns 1 if the queue is empty, 0 if it is not) e. Size (returns the size of the list)8. You must free memory appropriately. Namely, when you dequeue, you’ll free memory for a node, but you will NOT free memory for the customer. You will free this memory a bit later right after you calculate when that customer will finish checking out.Important note and hints: – This assignment is challenging not because it’s algorithmically difficult, but because there are many small rules that don’t necessarily have a “clean” implementation. – This means you need to get started early!!! (On average, I think this assignment will take twice as long as assignment #1.) – As suggested, you must implement a queue of customer using linked list like the way discussed in the class for int. That will be your main base. – Have an array of static queue of size 12 and don’t forget to initialize each of them. – Load all the data into the array of queues based on the rules. – List all the nonempty queues into an array and then use the length of the array and number of booths to do the calculations which items from that array will belong to booth 1, booth 2, etc. – A good idea would be calculating how many customers a booth will serve and run a loop to serve the customers belong to that booth.
