Problem 1. Suppose we modify the multiplicative weights algorithm for the best expert problem given in the lecture notes so that the weight update step is ωt+1(i) := ωt(i)(1 − ϵct(i)) (rather than ωt+1(i) := ωt(i)(1−ϵ) ct(i) ). Show that this algorithm also has regret O( p T lnn).Problem 2. Consider a first-price auction with two bidders, whose valuations are i.i.d. with uniform distribution, i.e., vi ∼ Uniform[0,1]. Let µi (vi) be the bid of bidder i when its valuation is vi . Assume that the bidders use only affine µi , i.e., µi (vi) = cvi +d. Find c, and d such that © µi ,i = 1,2ª form a Bayesian-Nash equilibrium for this game.Problem 3. Consider the following Cournot competition with I firms. For each firm i, the strategy is to choose a quantity qi ∈ (0,∞), and the payoff function is ui(qi ,q−i) = qi(P(Q)−c), where P(Q) with Q = PI i=1 qi denotes the inverse demand (price) function.Show that this game is an ordinal potential game. The definition of ordinal potential game is as follows: An ordinal potential game exists if there is a potential function Φ : S → R such that for all agents i with strategy si , Φ(si ,s−i)−Φ ¡ s ′ i ,s−i ¢ > 0 iff ui (si ,s−i)−ui ¡ s ′ i ,s−i ¢ > 0.Problem 4. Consider an online learning setting where loss vectors ℓ 1 ,ℓ 2 ,… ∈ [0,1]d are observed. Prove that we could always choose weights w 1 ,w 2 ,… ∈ ∆ d (probability simplex) so that ∀ϵ > 0, ∃T s.t. 1 T Ã X T t=1 ℓ t ·w t − X T t=1 ℓ t i ! ≤ ϵ, ∀i.(Hint: Reduce the above problem to apply the Blackwell Approachability Theorem. Utilize the equivalence between the following two conditions: (1) ∀q∃p s.t. r (p,q) ∈ S; and (2) For all half-spaces H containing S, ∃p s.t. ∀q, r (p,q) ∈ H.)Problem 5. Prove the revenue equivalence theorem between second-price auction and allpay auction for N bidders with i.i.d. uniform distribution vi ∼ Uniform[0,1] on single item. In all-pay auction, each bidder pay his/her bid, regardless of whether being allocated, and the bidder with the highest bid is allocated the item. (Hint: First prove the equilibrium bidding function is bi(vi) = N−1 N v N i .)
Problem 1. [Cournot Competition] Consider two companies, say company 1 and company 2, which produce identical products. In the Cournot model of competition, companies decide the amount they produce and the market determines a price depending on the total amounts of the products available in the market. The price is higher if the amount of the product is smaller. Let ai(i = 1,2) ∈ [0,∞) denote the amount of the product produced by company i. Assume that producing one unit of the product costs each company $1, and the sales price per unit of the product is determined as [2−(a1 + a2)]+. Thus, the payoffs of company 1 and company 2 are given by u1(a1,a2) = a1[2−(a1 + a2)]+ − a1 u2(a1,a2) = a2[2−(a1 + a2)]+ − a2, respectively. Fine a pure Nash Equilibrium for this game.Problem 2. [Bertrand Competition] The Bertrand model is an alternative to the Cournot model of competition. In the Bertrand model, again we consider two companies only, but now each company sets a price and the demand for the product is a function of the lower of the two companies’ prices. More precisely, each company i sets a price pi for the product.The demand for the product is a function of the prices as follows: if company i sets its price lower than that of the other company, i.e., pi < p−i , the demand for the product of company i is given by f (pi) units, and the demand for the product of the other company is zero. If pi = p−i , then the demand is f (pi)/2 for both companies. Let ci be the cost for company i toproduct one unit of the product. Then, the payoff for company i is given by ui(pi ,p−i) = f (pi)(pi −ci) if pi < p−i , f (pi)(pi −ci)/2 if pi = p−i 0 otherwise, show that when c1 = c2 = c, p1 = p2 = c is the unique NE.Problem 3. Consider the following Pigou network: show that the price of anarchy (POA) when CB (x) is of the form ax2 +bx +c,a,b,c > 0 is upper bounded by 3 p 3 3 p 3−2 .Problem 4. Consider a graph with a set of nodes V and a set of edges E. Let ce denote the cost of using edge e ∈ E. This graph is accessed by a set of players, where each player chooses to occupy a set of edges. If there are fe players occupying an edge e, the cost to each such player is ce fe . Let Ri be the set of edges occupied by player i. Then its cost is given by Ci (Ri ,R−i) = P e∈Ri ce fe (Ri ,R−i) . A Nash equilibrium for this problem is a set ¡ Rˆ 1,…,Rˆ n ¢ if there are n players such that Ci ¡ Ri ,Rˆ−i ¢ ≥ Ci ¡ Rˆ i ,Rˆ−i ¢ ,∀Ri .Moreover, global optimal solution to this game is a set ¡ R ∗ 1 ,…,R ∗ n ¢ such that P i Ci ¡ R ∗ i ,R ∗ −i ¢ ≤ P i Ci (Ri ,R−i),∀(Ri ,R−i). 1. Show that P i Ci (Ri ,R−i) = P e:fe (Ri ,R−i)≥1 ce .2. Show that there exists a Nash equilibrium ¡ Rˆ 1,…,Rˆ n ¢ such that X i Ci ¡ Rˆ i ,Rˆ−i ¢ ≤ µ 1+ 1 2 +…+ 1 n ¶X i Ci ¡ R ∗ i ,R ∗ −i ¢ Hint: Use the potential function used in the congestion game described in the class to classify the Nash equilibrium of this game.Problem 5. (1) Use Rosen’s theorem to prove the following result: consider a zero-sum game, where U2(a1,a2) = −U1(a1,a2). Assume U1 is strictly concave in a1, and strictly convex in a2. Then there exists a unique SP and the SP is in pure strategies (Note: SP= saddle point); (2) During the prove of Rosen’s theorem, Why did we have to define the functions L(v,a)?
Problem 1. Show that the two-player game illustrated in the following has a unique equilibrium. (Hint: Show that it has a unique pure-strategy equilibrium; then show that player 1, say, cannot put positive weight on both U and M; then show that player 1, say, cannot put positive weight on both U and D, but not on M, for instance.) L M R U 1,−2, −2,1 0,0 M −2,1 1,−2 0,0 D 0,0 0,0 1,1 Problem 2. Let X and Y be subsets of some vector space. Let f (x, y) be a function from X ×Y to R. Show that supx∈X infy∈Y f (x, y) ≤ infy∈Y supx∈X f (x, y).Problem 3. Find a saddle point and the value of the following zero-sum game: 4 3 1 4 2 5 6 3 1 0 7 0 Please show all the steps you used in obtaining the saddle point, such as the relevant LPs. If you used a computer program, please attach a copy of the program.Problem 4. Repeat Problem 3 for the following matrix: 0 5 −2 −3 0 4 6 −4 0 Problem 5. Find all the NE of the following two-person nonzero-sum game b1 b2 b3 b4 a1 (−2,2) (0,−4) (11,−5) (5,−6) a2 (−4,0) (−1,−1) (11,−2) (4,−3) a3 (−5,3) (−5,2) (10,0) (3,1) a4 (−6,2) (−7,1) (1,0) (2,3)Problem 6. Consider the following nonzero game. Let (x ∗ , y ∗ ) and (xˆ, yˆ) be two mixed strategy Nash equilibria of this game. Show that (x ∗ , yˆ) and (xˆ, y ∗ ) are also Nash equilibria. (Hint: Consider the sum of the payoffs of the two players.) L R U (4,−2) (−3,5) D (10,−8) (0,2)Problem 7. Prove Farka’s Lemma. Let A ∈ R m×n and b ∈ R m×1 . Then exactly one of the following two conditions holds: (1) ∃x ∈ R n×1 such that AX = b, x ≥ 0; (2) ∃y ∈ R 1×m such that A T y ≥ 0, y T b < 0;Problem 8. Prove Brouwer fixed-point theorem for one-dimensional case. Let C ∈ R be a convex, closed and bounded set. Let f : C → C be a continuous function. Then f has a fixed point, i.e., ∃x ∈C such that x = f (x).
The purpose of this assignment is to get you familiar with sentiment classification. By the end of this assignment, you will have your very own “Sentiment Analyzer”. You are given a Large Movie Review Dataset that contains a separate labeled train and test set. Your task is to train a Naïve Bayes classifier on the train set and report accuracy on the test set.Dataset: The core dataset contains 50,000 reviews split evenly into 25k train and 25k test sets. The overall distribution of labels is balanced (25k pos and 25k neg). There are two top-level directories [train/, test/] corresponding to the training and test sets. Each contains [pos/, neg/] directories for the reviews with binary labels positive and negative. Within these directories, reviews are stored in text files named following the convention [[id]_[rating].txt] where [id] is a unique id and [rating] is the star rating for that review on a 1-10 scale.For example, the file [test/pos/200_8.txt] is the text for a positive-labeled test set example with unique id 200 and star rating 8/10 from IMDb. The dataset can be downloaded from here.Preprocessing: In the preprocessing step you’re required to remove the stop words and punctuation marks and other unwanted characters from the reviews and convert them to lower case. You may find the string and regex module useful for this purpose. A stop word list is provided with the dataset.Part 1: Implement Naïve Bayes for sentiment analysis from scratch keeping in view all the discussions from the class lectures. Feel free to read Chapter 4 (Section 4.1, 4.2, 4.3) of the Speech and Language Processing book to get an in-depth insight into the Naïve Bayes classifier. Use Bag-of-words representation and apply Laplace (Add-1) smoothing as discussed in the class lectures. Specifically, you will need to implement the following algorithm: Report accuracy and confusion matrix. The expected accuracy on the test set is around 80%.Part 2: Use scikit-learn’s CountVectorizer to transform your train and test set to bag-of-words representation and Naïve Bayes implementation to train and test the Naïve Bayes on the provided dataset. Use scikit-learn’s accuracy_score function to calculate the accuracy and confusion_matrix function to calculate the confusion matrix on the test set.
With the assumption that you can compromise the victim’s machine (you need to do this), try to redirect www.randomurl.comto any IP address of your choice.A few things to note: 1. The host name and IP address pairs in the hosts file [/etc/hosts] are used for local lookup. 2. The host file is ignored by the dig command, but will take effect on the ping command and web browser.Here’s a visual representation of this attack: Submission for this task: Compare the results of redirection both before and after the attack Provide screenshots of the edited host file. Provide before and after attack screenshots of ping www.randomurl.com. Please also list the important code snippets followed by explanation. Simply attaching code without any explanation will not receive credits.In this attack, the victim’s machine has not been compromised so you cannot directly change the DNS query process on the victim’s machine. However, as you might already know, if the attacker is on the same local area network as the victim, they can still cause problems.In this task, you will spoof a fake DNS response. The criteria the DNS response must follow in order to be accepted by the user’s computer is as follows: The source IP address must match the IP address of the DNS server The destination IP address must match the IP address of the user’s machine The source port number, which is also known as the UDP port, must match the port number that the DNS request was sent to [this is usually port 53] The destination port number must match the port number the DNS request was sent from The UDP checksum must be correct The transaction ID must match the transaction ID in the DNS request The domain name in the question section of the response must match the domain name in the question section of the request The domain name in the answer section must match the domain name in the question section of the DNS request The user’s computer must receive the fake DNS reply before it receives the legitimate DNS responseNetwox tool 105 or Netwag tool 105 lets you conduct the type of sniffing and responding required in this case. You can limit the scope of your sniffing to packets only from a particular host by setting respective flags of these tools. Netwag tool 105 is a gui version of Netwox tool.The manual of the Netwox tool is: The interface of Netwag 105 is as follows: Additional Question: why is this attack not efficient? Here’s a visual representation of this attack:Submission for this task: Compare the results of the dig command obtained both before and after the attack. Provide screenshots throughout along with explanation of what you are doing Answer the additional question Please also list the important code snippets followed by explanation. Simply attaching code without any explanation will not receive credits.When a DNS server X receives a query, it checks its cache; if the hostname is there, the server will simply reply with the information from its cache. If not, the server will ask another DNS server for the information. Once it gets the answer from another DNS server, it stores the answer in the cache for future queries.In this task, you will be exploiting this and performing DNS cache poisoning. You will spoof the response from the other DNS servers so the DNS server X will keep the spoofed response in its cache for a certain time period. Next time, when a user’s machine wishes to resolve the same hostname, DNS server X will use the spoofed response present in the cache to reply. You can use the same tool Netwox 105 or Netwag 105 for this task. However, before attacking, please make sure the DNS cache is empty.You can flush the cache using this command: sudo rndc flush A few things to note: 1. Select raw in the spoofip field or else Netwox 105 will try to also spoof the MAC address for the spoofed IP address and your attack might not work.2. You can determine if the DNS server is poisoned or not by observing the DNS traffic using wireshark when you run the dig command on the target hostname.Submission for this task: Compare the results obtained both before and after the attack Provide screenshots throughout along with explanation of what you are doing Please also list the important code snippets followed by explanation. Simply attaching code without any explanation will not receive credits.Section 3 Guidelines: Please download the zip folder for this section from the link given below: https://drive.google.com/file/d/1jqRhgIvQa7sFFZrkfOr1TahpDCEYrnnF/viewQuestion 3.1 [20 Marks] For this question, you need tools that are part of Kali Linux. You can download the VM image from the following link: https://www.osboxes.org/kali-linux/#kali-linux-2020-4-vbox Please download Kali Linux 2018.4 Username: root Password: osboxes.orgSketchyCorp employees connect to the wireless network using WPA2-PSK security. Our goal is to break into their network. We have managed to find a capture of their WiFi authentication handshake, which can be found as wpa2.pcap (in the zip file). We have also managed to determine that the password is in the form of either cos432-XYZ or COS432- XYZ (X, Y, and Z are alphanumeric characters [a-z, A-Z, 0-9])Answer the following questions: How many possible Wi-Fi passwords are there that fulfills the password format? What is the actual Wi-Fi password used? How did you obtain that password?Make sure you add a detailed description of all the steps you took and the reason for doing so. Additionally, also add screenshots. The following links will be helpful: 3. https://null-byte.wonderhowto.com/how-to/hack-like-pro-crack-passwords-part-4-creat ing-custom-wordlist-with-crunch-0156817/ 4. https://tools.kali.org/wireless-attacks/aircrack-ngQuestion 3.2 [40 Marks] The goals of this question are to build up your familiarity with both how real network attacks manifest and how to effectively employ some widely available tools for analyzing network activity. The forensic questions are designed to not require exhaustive manual analysis to answer. You need to use Wireshark to carry out your investigations.You can read about Wireshark from relevant section of the document given in the following link: https://drive.google.com/file/d/1KtpOf1Oas0ux8wR5wr6fWN86dHJEE9Vi/view Further, some questions require the knowledge of specific header fields (which we might not have talked about in the class) to locate a “needle in the haystack.” We recommend that you spend some time thinking about your analysis plan before diving into a question, i.e., how you can efficiently explore the logs. This process might benefit from some (often light) web surfing to get ideas about how to locate particular features. In general, we anticipate that the biggest pitfall for completing this question effectively is the temptation to poke through the logs “blindly” rather than thoughtfully. That often won’t work effectively here — and in actual practice will work even less well because the logs you’ll encounter in real life will be much larger than those here.Submission Instructions (for this question): You will be examining a different scenario in each problem. For each scenario, you will submit a summary of your forensic analysis. Use the questions in each problem as a road map to present your case. We expect you to provide as strong a case as you can by including the relevant information from the log files formatted according to the following skeleton: For scenarios 1 and 5: Answer the questions listed in the scenario. For scenario 3 and 4: List the following. 1. Name of the attack 2. Attacker: IP address and domain (if relevant) 3. Victim: User account, document, IP address 4. The action of the attacker: description supported by evidence from the relevant log files.For scenarios involving vulnerability: Vulnerability: description of the vulnerability IPs of vulnerable hosts supported by evidence (e.g., a successful attack)Scenarios and Traces: This forensic investigation relates to Huge Big Dairy, a farming and poultry conglomerate runout in Madison, Wisconsin. They pride themselves on their yogurts, brie cheeses, and buffalo wings (made out of Real Buffalo). Huge Big’s CEO, Chuck “Mondo” Cheeze, brashly trumpets his company’s expertise, not only in all things dairy, but their e-marketing prowess and home-grown Internet security savvy. Synonymous decides to humiliate HBDairy, exposing their secrets and incompetence, and disrupting the activity of their employees. In a series of Internet attacks that HBDairy finds itself powerless to counter, Synonymous deeply embarrasses the company. Eventually, HBDairy must admit they have been out-matched, and in desperation, they turn to experts outside help: you.They commission your team to analyze how Synonymous Achieved Their Exploits. Luckily, the one facet of computer security they managed not to screw up is logging: they have full packet traces of all of the systems in question.The traces have been shared with you in the zip file and numbered according to the following scenarios. Wi-fi Connect Capture Investigate the s1 trace using Wireshark. The trace captures the Authentication and Association Phase of a station connecting to a wireless access point. 1. Why doesn’t the trace contain any IP packets? 2. What is the authentication type used by the Wireless Access Point? What are the security risks of this authentication mechanism?Here is a useful resource to understand the steps involved: The vulnerable DNS clients Recall that most DNS clients now select a random UDP source port when making DNS queries to help defend against the Kaminsky attack. When you mention this threat to the HBDairy IT staff, they reply, “The K-huh-what attack?” Thus, you view it as prudent to assess whether any of their clients making DNS queries lack UDP source port randomization. Analyze the s2 trace to assess the sequence of source ports seen for each resolver that makes more than one query. If you find they all appear to be okay, then list the resolvers you analyzed. If you find some that appear to not use randomization, list those and the corresponding evidence. The Mysterious wall post. One fine morning, an HBDairy employee noticed that a secret message he had sent last night to his colleague Fro Yo using Facebook messaging (i.e., sent to his friend’s inbox) was subsequently posted using his account on his friend’s wall. Examine the web traffic in the s3 trace to find evidence of the attack used for the wall post. Sketch the steps of the attacker. YouTube becomes NoTube. One of the competitive benefits that HBDairy provides to its employees is on-the-job access to YouTube. Lately, many disgruntled employees have complained that they have lost this benefit because their browser’s report page could not be loaded when they try to access YouTube. Analyze the web traffic in the s4 trace to find out how Synonymous disrupted the YouTube access. How much downtime did this result in? Emails in the clear The POP protocol is used for Email. Seems like one of the employees at HBDairy was taking a security course, as his email exchanges indicate. Investigate the s5 trace, and find out: What is the POP username and password? How many emails are in the user’s mailbox? Give the contents of from, to, subject, and date for each email.
You are not allowed to use scikit-learn or any other machine learning toolkit for this part. You have to implement your own k-NN classifier from scratch. You may use Pandas, NumPy, Matplotlib, and other standard Python libraries.Problem: The purpose of this assignment is to get you familiar with the k nearest neighbor classification. You are given the Apple Sentiment Tweets dataset that contains around 1630 tweets about Apple labeled as positive, neutral and negative in the form of 1, 0, and -1 respectively. Your task is to implement the k nearest classifier and use it for predicting the sentiments of the tweets about Apple.Dataset: The dataset contains around 1,630 tweets. There are only two columns in the dataset: Text: Contains the text of the tweet. Sentiment: Contains the sentiment of the tweet which is divided into three classes:1 (positive), -1 (negative), and 0 (neutral). Divide this dataset into training and testing sets based on an 80-20 split using python. Preprocessing: In the preprocessing step, you’re required to remove the stop words, punctuation marks, numbers, unwanted symbols, hyperlinks, and usernames from the tweets and convert them to lower case. You may find the string and regex module useful for this purpose. A stop word list is provided within the assignment.Feature Extraction: In the feature extraction step, you’ll represent each tweet as a bag-of-words (BoW), that is, an unordered set of words with their position ignored, keeping only their frequency in the tweet.For example, consider the below tweets: T1 = Welcome to machine learning! T2 = kNN is a powerful machine learning algorithm. 2 The bag-of-words representation (ignoring numbers, case, and punctuation) for the above tweets are: Vocabulary welcome to machine learning knn is a powerful algorithm T1 1 1 1 1 0 0 0 0 0 T2 0 0 1 1 1 1 1 1 1Note: We only use the training set to construct the vocabulary for the BoW representation.After you have preprocessed the data and created a bag of words, you have to implement the following tasks: 1. Create your own k-Nearest Neighbors classifier function by performing the following tasks: – For a test data point, find its distance from all training instances. – Sort the calculated distances in ascending order based on distance values. – Choose k training samples with minimum distances from the test data point. – Return the most frequent class of these samples. (Your function should work with Euclidean distance as well as Manhattan distance. Pass the distance metric as a parameter in the k-NN classifier function. Your function should also be general enough to work with any value of k.)2. Implement an evaluation function that calculates the classification accuracy, F1 score, and the confusion matrix of your classifier on the test set.3. Use 5- fold cross-validation on your training data. (In cross-validation, you divide the training data set into 5 parts. 4 parts will be used for training and 1 part will be used for validation. Then you will take a different part of your data as a validation data set and train your algorithm on the rest of the data set.) Run your k-NN function for this data for the values of k = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Do this for both the Euclidean distance and the Manhattan distance for each value of k.Formulas for both are listed below: Euclidean Distance: d(~p, ~q) = p (p1 − q1) 2 + (p2 − q2) 2 + (p3 − q3) 2 + … + (pn − qn) 2 Manhattan Distance: d(~p, ~q) = |(p1 − q1)| + |(p2 − q2)| + |(p3 − q3)| + … + |(pn − qn)| 4. For the even values of k given in the above task, break ties by backing off to the k-1 value. (For example, if you have k = 6 nearest neighbors and three of them havethe label ‘positive’ and three have the label ‘negative, then you will break off the tie by taking k=5 nearest neighbors. On the other hand, let’s say if you have k = 6 nearest neighbors where two have the label ‘positive’, two have the label ‘negative’, and two have the label ‘neutral’. In that case, k =5 will still lead to two labels having a draw in which case you will continue decreasing k until there is a clear winner.)5. Run your evaluation function for each value of k for both distance metrics, Report classification accuracy, F1 score, and confusion matrix.6. Present the results as a graph with k values on the x-axis and classification accuracy on the y-axis. Use a single plot to compare the two versions of the classifier (one using Euclidean and the other using Manhattan distance metric). Make another graph but with the F1 score on the y-axis this time. The graphs should be properly labeled.7. Comment on the best value of k you have found for both distance metrics using cross-validation.8. Finally, use the best value of k for both distance metrics and run it on the test data set. Find the F1 score, classification accuracy, and confusion matrix and print them.In this part, you have to use scikit-learn’s k-NN implementation to train and test your classifier on the dataset used in Part 1. Repeat the tasks you have done in Part 1 but this time using scikit-learn. Use your bag of words to do cross-validation and run the k-NN classifier for values of k = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 using both Euclidean and Manhattan distance.Use scikit-learn’s accuracy_score function to calculate the accuracy, classification_report to calculate macro-average (precision, recall, and F1), and confusion_matrix function to calculate confusion matrix for test data. Also present the results as a graph with k values on the x-axis and performance measures on the y-axis just like you did in part 1.Use a single plot to compare the two versions of the classifier (one using Euclidean and the other using Manhattan distance metric). Finally, print the best values of k for both distance metrics. Then use this value of k on the test data set and print the evaluation scores.
In this part, you have been contacted by the National Cyber Security Division of Pakistan, they need your expertise for a matter of utmost attention. Recently, a twitter account has surfaced which is propagating hate against Pakistan by statements like this: Fortunately, you have gotten access to the program running this account, which is an executable binary file “bot”.You were first suggested to just stop this twitter account, but you have realized that it would be a better idea to use it for putting out good words for Pakistan. However, you can’t change the code for the bot since you don’t have access to it. Here we introduce you to a new tool called Frida. Frida is a state of the art scripting utility being used by hackers and academics alike in the world, and is quite loved in the CTF community, due to its power across Android, Iphone and native code. Frida af ects the code in real time, therefore, make sure that the “bot” is running, when you run the Frida scripts.You can install frida by going to your console and typing: $ pip install frida-tools Then run the following in your command line: $ sudo sysctl kernel.yama.ptrace_scope=0 It allows tracing non-child processes on linux. You know that this bot is calling a function named “tweet”, whose argument decides what the bot would tweet.You can run a python script “recon.py”(which is provided to you) to understand what kind of argument the “tweet” is receiving. Then you will use a frida script “attack.py” to change these arguments and make the bot tweet its immense admiration for Pakistan (Try 3,4 different arguments). If you use the right argument, you can see the output of the program change in real time. In return, the National Cyber Security Division will appoint its chief security analyst (if you want, of course).Submission Guidelines: 1. Submit the attack.py file along with a screenshot of the desired output.Let’s start easy and have a look at defenses. You have been provided with a file called ‘defenses.py’. This file implements a very (very) simple version of a program running simulator. You are supposed to implement the defenses in this file. Be careful to read instructions in the file carefully and only modify portions you are allowed to modify. For this task you need to add the following defenses into defenses.py file: 1. ASLR 2. StackGuards (Stack Canaries) 3. Non-executable Stack Further instructions are given in the defenses.py and task2_guide.pdf files.Tip: To have a better understanding, I recommend reading through all of the code in the file. Printing program memory after each instruction may assist you in understanding what is going on. Submission Guidelines: 1. Submit the defenses.py file for this task.Turning Off Counter-measures Ubuntu and other Linux distributions have implemented several security mechanisms to make the buffer-overflow attack difficult. To simplify our attacks, we need to disable them first. Later on, we will enable them one by one, and see whether our attack can still be successful.Address Space Randomization Ubuntu and several other Linux-based systems use address space randomization to randomize the starting address of the heap and stack. This makes guessing the exact addresses difficult; guessing addresses is one of the critical steps of buffer-overflow attacks. In this task, we disable this feature using the following command: $ sudo sysctl -w kernel.randomize_va_space=0The StackGuard Protection Scheme The GCC compiler implements a security mechanism called StackGuard to prevent buffer overflows. In the presence of this protection, buffer overflow attacks will not work. We can disable this protection during the compilation using the -fno-stack-protector option.For example, to compile a program example.c with StackGuard disabled, we can do the following: $ gcc -fno-stack-protector example.c Non-Executable Stack Ubuntu used to allow executable stacks, but this has now changed: the binary images of programs (and shared libraries) must declare whether they require executable stacks or not, i.e., they need to mark a field in the program header. Kernel or dynamic linker uses 3 this marking to decide whether to make the stack of this running program executable or non-executable. This marking is done automatically by the recent versions of gcc, and by default, stacks are set to be non-executable. To change that, use the following option when compiling programs: 1. For executable stack $ gcc -z execstack -o test test.c 2. For non-executable stack: $ gcc -z noexecstack -o test test.c Because the objective of this task is to show that the non-executable stack protection does not work, you should always compile your program using the “-z noexecstack” option in this lab.Configuring /bin/sh In Ubuntu 16.04, the /bin/sh symbolic link points to the /bin/dash shell. The dash shell in Ubuntu 16.04 has a countermeasure that prevents itself from being executed in a Set-UID process. Basically, if dash detects that it is executed in a Set-UID process, it immediately changes the effective user ID to the process’s real user ID, essentially dropping the privilege. The dash program in Ubuntu 12.04 does not have this behavior. Since our victim program is a Set-UID program, and our attack relies on running /bin/sh, the countermeasure in /bin/dash makes our attack more difficult.Therefore, we will link /bin/sh to another shell that does not have such a countermeasure. We use the following commands to link /bin/sh to zsh: $ sudo ln -sf /bin/zsh /bin/sh Different Environment Variables while running GDB This is the layout of your program on the memory.If the environment variables inside the gdb could be different from those in your shell, it will mess up the addresses that you will be using for the Buffer Overflow Attack. You can checkout the environment variables in your shell using: $ env And inside the GDB using gdb-peda$ show env Usually GDB adds two new environment variables LINES and COLUMNS. You can unset them using: gdb-peda $ unset LINES gdb-peda $ unset COLUMNS Make sure that the environment variables are the same inside and outside the gdb, to make sure that your attacks work outside of gdb as well.The Vulnerable Program The program provided to you in the ‘retlib.c’ file has a buffer overflow vulnerability. It first reads an input of size 300 bytes from a file called badfile into a buffer of size BUF SIZE, which is less than 300. Since the function fread() does not check the buffer boundary, a buffer overflow will occur. This program is a root-owned Set-UID program, so if a normal user can exploit this buffer overflow vulnerability, the user might be able to get a root shell. It should be noted that the program gets its input from a file called badfile, which is provided by users. Therefore, we can construct the file in a way such that when the vulnerable program copies the file contents into its buffer, a root shell can be spawned. Compilation Let us first compile the code and turn it into a root-owned Set-UID program. Do not forget to include the -fno-stack-protector option (for turning off the StackGuard protection) and the “-z noexecstack” option (for turning on the non-executable stack protection). It should also be noted that changing ownership must be done before turning on the Set-UID bit, because ownership changes cause the Set-UID bit to be turned off: $ gcc -fno-stack-protector -z noexecstack -o retlib retlib.c $ sudo chown root retlib $ sudo chmod 4755 retlibStep 1: Finding out the addresses of libc functions In Linux, when a program runs, the libc library will be loaded into memory. When the memory address randomization is turned off, for the same program, the library is always loaded in the same memory address (for different programs, the memory addresses of the libc library may be different). Therefore, we can easily find out the address of system() using a debugging tool such as gdb. Namely, we can debug the target program retlib. Even though the program is a root-owned Set-UID program, we can still debug it, except that the privilege will be dropped (i.e., the effective user ID will be the same as the real user ID). Inside gdb, we need to type the run command to execute the target program once, otherwise, the library code will not be loaded. We use the p command (or print) to print out the address of the system() and exit() functions (we will need exit() later on). $ touch badfile $ gdb -q retlib gdb-peda$ run gdb-peda$ p system $1 = {} 0xb7e42da0 gdb-peda$ p exit $2 = {} 0xb7e369d0 gdb-peda$ quit It should be noted that even for the same program, if we change it from a Set-UID program to a non-Set-UID program, the libc library may not be loaded into the same location.Therefore, when we debug the program, we need to debug the target Set-UID program; otherwise, the address we get may be incorrect. Submission Guidelines 1. Submit the Addresses of both these functions in the PDF FileStep 2: Putting the shell string in the memory Our attack strategy is to jump to the system() function and get it to execute an arbitrary command. Since we would like to get a shell prompt, we want the system() function to execute the “/bin/sh” program. Therefore, the command string “/bin/sh” must be put in the memory first and we have to know its address (this address needs to be passed to the system() function). There are many ways to achieve these goals; we choose a method that uses environment variables. You are encouraged to use other approaches. When we execute a program from a shell prompt, the shell actually spawns a child process to execute the program, and all the exported shell variables become the environment variables of the child process.This creates an easy way for us to put some arbitrary string in the child process’s memory. Let us define a new shell variable MYSHELL, and let it contain the string “/bin/sh”. From the following commands, we can verify that the string gets into the child process, and it is printed out by the env command running inside the child process. $ export MYSHELL=/bin/sh $ env | grep MYSHELL MYSHELL=/bin/sh We will use the address of this variable as an argument to system() call. The location of this variable in the memory can be found out easily using the following program: void main(){ char* shell = getenv(“MYSHELL”); if (shell) printf(“%x ”, (unsigned int)shell); } If the address randomization is turned off, you will find out that the same address is printed out. However, when you run the vulnerable program retlib, the address of the environment variable might not be exactly the same as the one that you get by running the above program; such an address can even change when you change the name of your program (the number of characters in the file name makes a difference). The good news is, the address of the shell will be quite close to what you print out using the above program.Therefore, you might need to try a few times to succeed. Step 3: Exploiting the buf er-overflow vulnerability We are ready to create the contents of badfile. Since the content involves some binary data (e.g., the address of the libc functions), we can use C or Python to do the construction. Using Python We provide you with a skeleton of the code, with the essential parts left for you to fill out. You need to figure out the three addresses and the values of X, Y, and Z. If your values are incorrect, your attack might not work. In your report, you need to describe how you decide the values for X, Y and Z.Either show us your reasoning or, if you use a trial-and-error approach, show your trials. Using C We provide you with a skeleton of the code, with the essential parts left for you to fill out. You need to figure out the addresses in lines marked by ✰, as well as to find out where to store those addresses (i.e., the values for X, Y, and Z). If your values are incorrect, your attack might not work. In your report, you need to describe how you decide the values for X, Y and Z. Either show us your reasoning or, if you use a trial-and-error approach, show your trials After you finish the above program, compile and run it; this will generate the contents for badfile. Run the vulnerable program retlib. If your exploit is implemented correctly, when the function bof() returns, it will return to the system() function, and execute system(“/bin/sh”). If the vulnerable program is running with the root privilege, you can get the root shell at this point. $ gcc -o exploit exploit.c $./exploit // create the badfile $./retlib // launch the attack by running the vulnerable program #
In this project, you will be using cryptographic libraries to decrypt multiple types of ciphers, break them, and launch attacks on widely used cryptographic hash functions. In 3.1.2, you will be decrypting ciphers with given ciphertexts and key values. Then, you will use the same technique to break a weak cipher with a limited key space.In 3.1.6, you will build a weak hash algorithm and find a collision for a given string. In 3.2.1, we will guide you through attacking the authentication functionality of an imaginary server API. The attack will exploit the length-extension vulnerability of hash functions in the MD5 and SHA1&2 families. In 3.2.2, you will use a cryptanalyst tool to generate different messages with the same MD5 hash value (collisions). You’ll then investigate how that capability can be exploited to conceal malicious behavior in software. In 3.2.3, you will implement another attack on RSA. Last, in 3.2.4, you will use a collision attack to generate two certificates with different public keys, but have identical RSA signatures.Objectives: • Become familiar with existing cryptographic libraries and how to utilize them • Understand pitfalls in cryptography and appreciate why you should not write your own cryptographic libraries • Execute a classic cryptographic attack on MD5 and other broken cryptographic algorithms • Execute a length-extension attack similar to a historical attack executed successfully against Flickr.Guidelines • You SHOULD work in a group of 2. • You MUST use Python 3.5 or higher. • Your answers may or may not be the same as your classmates’. • All the necessary files to start the assignment are on LMS. You MUST submit your answers in the files with the naming convention mentioned in the question. • It is highly recommended that you work in a python virtual environment. It is super simple and it will save you a lot of headache later.Python3 tutorial In this section, you will be writing several python3 scripts to do string encoding and manipulations needed to correctly read our input files and submit your answers. Reading .hex files In the later parts of this MP, you will be reading in .hex files, which are plaintext files containing an ASCII string representation of a single hexadecimal number. This is the content of an example .hex file: 3dab821d92b5ca7f48beee066996b8abc82f7e5646a0561710ea5bc11c80The following Python3 code snippet will read the contents of the file as a string and store it in file_content: # strip() remove any leading or trailing whitespace characters with open(‘file_name’) as f: file_content = f.read().strip() From here, there’s a number of things that you could do. Depending on the cryptographic library that you are using, you may need to use different data types, but here we list the most common conversions that you may need: # parse the string into a bytes object representing the hexadecimal number binary_content = bytes.fromhex(file_content) # parse the string into integer integer_parsed = int(file_content,16) # parse an integer to a hex string and remove the leading ‘0x’ str = hex(integer_parsed)[2:] # parse an integer to a binary string and remove the leading ‘0b’ str = bin(integer_parsed)[2:] 3 3.1.1 Exercise (2 points) (Difficulty: Easy)Files 1. 3.1.1_value.hex: an ASCII string representing a hexadecimal value Based on what you learned in the previous section, we want to to convert the given value into different representations and submit them in the specified files.What to submit 1. Convert the value in 3.1.1_value.hex to decimal and submit the decimal number as a string in sol_3.1.1_decimal.txt 2. Convert the value in 3.1.1_value.hex to binary and submit the binary number as a string in sol_3.1.1_binary.txt Symmetric Encryption, Public Key Encryption, and Cryptographic Hashes In this section, you will be writing your own cryptographic library to decrypt a substitution cipher, and using existing cryptographic libraries to experiment with a symmetric encryption called AES and a public key encryption called RSA. 3.1.2 Substitution Cipher (4 points) (Difficulty: Easy)Files 1. 3.1.2_sub_key.txt: key 2. 3.1.2_sub_ciphertext.txt: ciphertext sub_key.txt contains a permutation of the 26 uppercase letters that represents the key for a substitution cipher. Using this key, the ith letter in the alphabet in the plaintext has been replaced by the ith letter in 3.1.2_sub_key.txt to produce ciphertext in 3.1.2_sub_ciphertext.txt. For example, if the first three letters in your 3.1.2_sub_key.txt are ZDF…, then all As in the plaintext have become Zs in the ciphertext, all Bs have become Ds, and all Cs have become Fs. The plaintext we encrypted is a clue from the game show Jeopardy and has only uppercase letters, numbers and spaces. Numbers and spaces in the plaintext were not encrypted; they appear exactly as they did in the plaintext. Your task is to write a Python3 script in sol_3.1.2.py that decrypts a substitution ciphertext with a given key and writes the plaintext to a specified file. Your script must take three arguments from the command line: the ciphertext file, the key file, and the output file. We will run your script as follows: $ python3 your_script.py ciphertext_file key_file output_fileAdditionally, you have to submit the plaintext, which is obtained by using the key 3.1.2_sub_key.txt to decrypt 3.1.2_sub_ciphertext.txt, in the file sol_3.1.2.txt.What to submit Your Python3 script in sol_3.1.2.py and your plaintext in sol_3.1.2.txt 3.1.3 AES: Decrypting AES (4 points) (Difficulty: Easy) Files 1. 3.1.3_aes_key.hex: key 2. 3.1.3_aes_iv.hex: initialization vector 3. 3.1.3_aes_ciphertext.hex: ciphertext 3.1.3_aes_key.hex contains a 256-bit AES key represented as an ASCII string of hexadecimal values. 3.1.3_aes_iv.hex contains a 128-bit initialization vector in a similar representation. We encrypted a Jeopardy clue using AES in CBC mode using this key and initialization vector and wrote the resulting ciphertext (also stored in hexadecimal) to 3.1.3_aes_ciphertext.hex. Create a Python3 script named sol_3.1.3.py that decrypts the ciphertext using the provided information and outputs the plaintext to a specified file. Your script must take four arguments from the command line: the ciphertext file, the key file, the initialization vector file, and the output file. We will run your script as follows: $ python3 your_script.py ciphertext_file key_file iv_file output_fileCryptographic Library For this Assignment, we allow PyCryptodome, an open-source crypto library. PyCryptodome can be installed using pip3 with pip3 install -U PyCryptodome. What to submit Your Python3 script in sol_3.1.3.py and the decrypted message in sol_3.1.3.txt. 3.1.4 AES: Breaking A Weak AES Key (4 points) (Difficulty: Easy)Files 1. 3.1.4_aes_weak_ciphertext.hex: ciphertext As with the last task, we encrypted a Jeopardy clue using 256-bit AES in CBC mode and stored the result in hexadecimal in the file 3.1.4_aes_weak_ciphertext.hex. But for this task, we haven’t supplied the key. All we will tell you about the key is that it is 256 bits long and its 251 most significant (leftmost) bits are all 0s. The initialization vector was set to all 0s. First, find all plaintexts in the given key space. Then, you will review the plaintexts to find the correct plaintext that is the Jeopardy clue and the corresponding key.What to submit Find the key of the appropriate plaintext and submit it as a hex string in sol_3.1.4.hex. Remember that this AES key is 256 bits long.3.1.5 Decrypting a ciphertext with RSA (4 points) (Difficulty: Easy) Files 1. 3.1.5_RSA_private_key.hex: RSA private key (d) as hexadecimal string 2. 3.1.5_RSA_modulo.hex: RSA modulo (N) as hexadecimal string 3. 3.1.5_RSA_ciphertext.hex: an encrypted prime number that is encrypted with 1024-bit RSA as a hexadecimal stringIn this part, we used 1024-bit textbook RSA to encrypt a prime number using your public key and stored it in 3.1.5_RSA_ciphertext.hex as a hex string. Create a Python3 script named sol_3.1.5.py that takes as arguments the ciphertext, the private key, and the RSA modulo to compute the plaintext prime number and write it as a hex string to a specified file. We will run your script as follows: $ python3 your_script.py ciphertext_file key_file modulo_file output_file What to submit Your Python3 script in sol_3.1.5.py and the prime number as a hex string in sol_3.1.5.hex.Hash Functions This section will give you a chance to explore cryptographic hashing using existing cryptographic libraries and illustrate the potential pitfalls of writing your own cryptographic functions. 3.1.6 Weak Hashing Algorithm (6 points) (Difficulty: Medium)Files 1. 3.1.6_input_string.txt: input string Below you’ll find the pseudocode for a weak hashing algorithm we’re calling WHA. It operates on bytes (block size of 8 bits) and outputs a 32-bit hash.WHA: Input{inStr: a binary string of bytes} Output{outHash: 32-bit hashcode for the inStr as a series of hex values} Mask: 0x3FFFFFFF outHash: 0 for byte in input intermediate_value = ((byte XOR 0xCC) Left Shift 24) OR ((byte XOR 0x33) Left Shift 16) OR ((byte XOR 0xAA) Left Shift 8) OR (byte XOR 0x55)outHash = (outHash AND Mask) + (intermediate_value AND Mask) return outHashFirst, you’ll need to implement WHA in Python. Here are some sample inputs you can use to test your implementation: WHA(“Hello world!”) = 0x50b027cf and WHA(“I am Groot.”) = 0x57293cbbIn the file 3.1.6_input_string.txt, you’ll find another Jeopardy clue (surprise!). Your goal is to find another string that produces the same WHA output as this Jeopardy clue. In other words, demonstrate that this hash is not second preimage resistant.Find a string with the same WHA output as 3.1.6_input_string.txt and submit it in sol_3.1.6.txt. Also, submit the code for your implementation of the WHA algorithm in sol_3.1.6.py. Your Python3 script should take as arguments a text file and an output file, and outputs the WHA hash of the content of the file as a hex string in the specified file. We will run your script as follows: $ python3 your_script.py file.txt output_file What to submit Your Python3 script in sol_3.1.6.py and the collision string in sol_3.1.6.txt3.2 Advanced Tasks 3.2.1 Length Extension (15 points) (Difficulty: Medium) We have to be careful with the way we construct our Hash-based Message Authentication Codes (HMACs). HMACs use a symmetric key to guarantee a message’s integrity as well as ensure that only someone with the key could have generated the HMAC. Some HMAC constructions are subject to length extension attacks when using particular hash functions.Most of the hash functions we’ve discussed (MD5, SHA1, SHA256) use a design called the MerkleDamgård construction. Each is built around a compression function f and maintains an internal state s, which is initialized to a fixed constant. Messages are processed in fixed-size blocks by applying the compression function to the current state and the current block to compute an updated internal state, i.e. si+1 = f(si ,bi). The result of the final application of the compression function becomes the output of the hash function. Thus, the output of these hash functions also leaks the internal state of the algorithm!A consequence of this design is that if we know the hash of an n-block message, we can find the hash of longer messages by applying the compression function for each block bn+1,bn+2,… that we want to add. This process is called length extension.Experiment with Length Extension in Python To experiment with this idea, we’ll use a Python3 implementation of the MD5 hash function, though HMACs built with SHA-1 and SHA-256 can be vulnerable to length extension in the same way.You should have a pymd5.py module in your Git repository. Documentation for pymd5 is available by running $ pydoc pymd5. To follow along with these examples, run Python3 in interactive mode ($ python3 -i) and run the command from pymd5 import md5, padding.Consider the string “Use HMAC, not hashes”. We can compute its MD5 hash by running: m = “Use HMAC, not hashes” h = md5() h.update(m.encode()) print(h.hexdigest()) or, more compactly, print(md5(m).hexdigest()). The output should be: 3ecc68efa1871751ea9b0b1a5b25004dMD5 processes messages in 512-bit blocks, so internally the hash function pads m to a multiple of the 512-bit length. The padding consists of a 1 bit, followed by as many 0 bits as necessary, followed by a 64-bit count of the number of bits in the unpadded message. (If the 1 and count won’t fit in the current block, an additional block is added.) You can use the function padding(count ) in the pymd5 module to compute the padding that will be added to a count -bit message.Even if we didn’t know m, we could compute the hash of longer messages of the general form m + padding(len(m)*8) + suffix by setting the initial internal state of our MD5 function to MD5(m) instead of the default initialization value, and setting the function’s message length counter to the size of m plus the padding (a multiple of the block size). To find the padded message length, guess the length of m and run bits = (length_of_m + len(padding(length_of_m *8)))*8.The pymd5 module lets you specify these parameters as additional arguments to the md5 object: h = md5(state=”3ecc68efa1871751ea9b0b1a5b25004d”, count=512) Now you can use length extension to find the hash of a longer string that appends the suffix “Good advice”. Simply run: x = “Good advice” h.update(x) print(h.hexdigest())to execute the compression function over x and output the resulting hash. Verify that it equals the MD5 hash of str.encode(m) + padding(len(m)*8) + str.encode(x). Notice that, due to the length-extension property of MD5, we didn’t need to know the value of m to compute the hash of the longer string—all we needed to know was m’s length and its MD5 hash.This component is intended to introduce length extension and familiarize you with the MD5 module we will be using; you will not need to submit anything for it.Conduct a Length Extension AttackFiles 1. 3.2.1_query.txt: query 2. 3.2.1_command3.txt: command3 One example of when length extension causes a serious vulnerability is when people mistakenly try to construct something like an HMAC by using hash(secret ∥ message), where ∥ indicates concatenation. For example, Professor Vuln E. Rabble has created a web application with an API that allows client-side programs to perform an action on behalf of a user by loading URLs of the form: http://ece422.org/project3/api?token=b301afea7dd96db3066e631741446ca1&user=admin& command1=ListFiles&command2=NoOp where token is MD5(user’s 8-character password ∥ user=…. [the rest of the URL starting from user= ]). The domain name is given as an example, we did not set up a web server for this assignment. Text files with the query of the URL 3.2.1_query.txt and the command line to append3.2.1_command3.txt are provided. Using the techniques that you learned in the previous section and without guessing the password, apply length extension to create a new query in the URL ending with the command specified in the file, &command3=DeleteAllFiles, that is treated as valid by the server API. Submit this in the file named sol_3.2.1.txt This is a hint about what your final solution will look like: token=[updated MD5 hash]&user=admin&command1=OriginalCMD[percent-encoded padding]&command3=RebootCreate a Python3 script named sol_3.2.1.py that takes as a command line argument a filename containing a valid query in the URL and modifies it such that it will execute a DeleteAllFiles command as the user, then output the new query to a specified file. You may assume that the query string will always begin with the token. You SHOULD validate that your solution works by building test cases of your own–where you know the secret key. We will run your script as follows: $ python3 your_script.py query_file command3_file output_fileHint: You will want to use the quote_from_bytes() function from Python’s urllib.parse module to encode non-ASCII characters in the padding. Historical connection: In 2009, security researchers found that the API used by the photo-sharing site Flickr suffered from a length-extension vulnerability almost exactly like the one in this exercise. What to submit Your Python3 script in sol_3.2.1.py and the modified query in sol_3.2.1.txt.3.2.2 MD5 Collisions (15 points) (Difficulty: Medium) MD5 was once the most widely used cryptographic hash function, but today it is considered dangerously insecure. This is because cryptanalysts have discovered efficient algorithms for finding collisions—pairs of messages with the same MD5 hash value.The first known collisions were announced on August 17, 2004 by Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu. Here’s one pair of colliding messages they published: Message 1: d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 Message 2: d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 Convert each group of hex strings into a binary file. (On Linux, run $ xxd -r -p file.hex > file.) 1. What are the MD5 hashes of the two binary files? Verify that they’re the same. ($ openssl dgst -md5 file1 file2) 2. What are their SHA-256 hashes? Verify that they’re different. ($ openssl dgst -sha256 file1 file2)This component is intended to introduce you to MD5 collisions; you will not submit anything for it. Generating Collisions Yourself In 2004, Wang’s method took more than 5 hours to find a collision on a desktop PC. Since then, researchers have introduced vastly more efficient collision finding algorithms. You can compute your own MD5 collisions using a tool written by Marc Stevens that uses a more advanced technique.You can download the fastcoll tool here: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip (Windows executable) or http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5-1_source.zip (source code) If you are building fastcoll from source, you can compile using this command: g++ -I /usr/local/include -L /usr/local/lib -O3 *.cpp -lboost_filesystem -lboost_program_options -lboost_system -o fastcollYou will also need the Boost libraries. On Ubuntu, you can install these using apt-get install libboost-all-dev. On macOS, you can install Boost via the Homebrew package manager using brew install boost.1. Generate your own collision with this tool. How long did it take? ($ time ./fastcoll -o file1 file2) 2. What are your files? To get a hex dump, run $ xxd -p file. 3. What are their MD5 hashes? Verify that they’re the same. 4. What are their SHA-256 hashes? Verify that they’re different.This component is intended to introduce you to MD5 collisions; you will not submit anything for it. A Hash Collision Attack The collision attack lets us generate two messages with the same MD5 hash and any chosen (identical) prefix. Due to MD5’s length-extension behavior, we can append any suffix to both messages and know that the longer messages will also collide. This lets us construct files that differ only in a binary “blob” in the middle and have the same MD5 hash, i.e. pre f ix ∥ blobA ∥ su f f ix and pre f ix ∥ blobB ∥ su f f ix.We can leverage this to create two programs that have identical MD5 hashes but wildly different behaviors. We’ll use Python, but almost any language would do. Copy and paste the following three lines into a file called prefix: (Note: typing the below lines yourself may lead to an encoding mismatch and an error may occur when running the resulting Python3 code) #!/usr/bin/env python3 # -*- coding: latin-1 -*- blob = “”” and put these three lines into a file called suffix: “”” from hashlib import sha256 print(sha256(blob.encode()).hexdigest())Now use fastcoll to generate two files with the same MD5 hash that both begin with prefix. ($ fastcoll -p prefix -o col1 col2). Then append the suffix to both ($ cat col1 suffix > file1.py; cat col2 suffix > file2.py). Verify that file1.py and file2.py have the same MD5 hash but generate different output.Extend this technique to produce another pair of programs, good and evil, that also share the same MD5 hash. One program should execute a benign payload: print(“I come in peace.”) The second should execute a pretend malicious payload: print(“Prepare to be destroyed!”). Note that we may rename these programs before grading them.What to submit Two Python3 scripts named sol_3.2.2_good.py and sol_3.2.2_evil.py that have the same MD5 hash, have different SHA-256 hashes, and print the specified messages.3.2.3 Mining your Ps and Qs (25 points) (Difficulty: Hard) The “Pretty Bad Privacy” encryption tool, pbp.py, can be used to insecurely encrypt files to a 1024-bit RSA public key. 1 Each line of the moduli.hex file contains a 1024-bit RSA modulus, 10,000 of these in total. In 3.2.3_ciphertext.enc.asc you have been provided the ciphertext of a Jeopardy clue, which has been encrypted using PBP with one of the RSA moduli in the file, and public exponent e = 65537. Factoring any of the 1024-bit moduli before the assignment is due is infeasible; furthermore you don’t even know which one to start on!Sometimes, badly malfunctioning implementations of RSA fail to generate unique prime numbers.The RSA moduli in the provided list were generated without sufficient entropy, and some of them share common factors. If two RSA moduli share a common factor, it is trivial to compute their GCD and factor both moduli. Unfortunately, looping over all pairs of moduli does not scale well, so you’ll have some difficulty finishing the project unless you use a more efficient algorithm.Your task is to use the method described in the “Mining your Ps and Qs” paper,2 Section 3.3, to compute the pairwise GCDs of the RSA keys provided. Once you have discovered some RSA private keys, you can then attempt to use them to recover the RSA-encrypted AES session key and decrypt the rest of homework file and submit the plaintext in sol_3.2.3.txt. You may use the decrypt() function we provided in pbp.py. As parameters, it expects a Crypto.PublicKey.RSA object and the ciphertext we gave you.What to submit Your python3 script in sol_3.2.3.py and the decrypted message in sol_3.2.3.txt.3.2.4 Creating Colliding Certificates (20 points) (Difficulty: Hard) The ECE 422 Certificate Authority issues TLS certificates, but charges for each signature. Your challenge is to rip off the CA by creating a pair of distinct (but valid) certificates, which both share the same signature from the CA.Since the CA signature can be based on the MD5 hash of the body of the ceritficate, you can use fastcoll to help you to create a collision. However, you also need to make sure that you know the private key corresponding to the RSA public key in each certificate. A method to achieve this is described in detail in Lenstra’s paper3 .To help you out, we have provided you with mp3-certbuilder.py, which is a script that uses the cryptography library and outputs a certificate with a random public key, with the fields to specific values, and signed by the ECE 422 CA (the CA’s private key is included in the script). You can run the script using the following command: 1PBP is a “hybrid encryption” mode. It uses 1024-bit RSA (with OAEP padding, rather than textbook RSA), to encrypt a random 256-bit key, and then uses this as an AES key to encrypt the (padded) message. 2https://factorable.net/weakkeys12.extended.pdf 3https://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf$ python3 mp3-certbuilder.py {roll number} {output filename}.cer This gives you an output certificate which you can view using the following command: $ openssl x509 -in {output filename}.cer -inform der -text -noout The certificate structure is shown below: Certificate: Data: Version: 3 (0x2) Serial Number: 4e:41:f2:89:eb:7b:92:ea:72:8c:d5:b5:41:82:a7:f4:3d:40:52:43 Signature Algorithm: md5WithRSAEncryption Issuer: CN=ece422 Validity Not Before: March 1 00:00:00 2017 GMT Not After : March 27 00:00:00 2017 GMT Subject: CN=amingni2, pseudonym=unused, C=US, ST=Illinois Subject Public Key Info: Public Key Algorithm: rsaEncryption Public-Key: (2048 bit) Modulus: 00:93:35:d1:0c:a1:11:a2:7c:53:38:7b:05:ab:3f: 39:69:de:58:e1:cd:43:af:dc:5e:93:00:9c:4e:18: 34:8e:86:17:0d:4e:be:06:63:69:34:ae:08:a1:a5: 0f:b6:fa:d8:d8:3f:c1:cc:a9:c8:2c:ea:01:4c:81: 55:7b:c7:a5:3f:57:3e:0b:a4:f9:ee:ba:4f:d3:bd: 46:e0:f8:ee:24:a0:d3:63:4d:9c:d8:65:aa:ad:98: 2d:ed:18:85:16:d7:64:53:58:e9:2b:20:2a:87:c2: 15:3b:b2:2e:06:57:23:b4:bd:91:3b:d0:8c:97:fb: 4e:ec:18:88:41:24:b2:45:ce:0c:1b:11:0b:54:10: 48:b3:3e:ca:fb:a0:94:dd:7e:20:a5:a6:92:72:1e: b6:3d:8a:81:eb:3b:41:94:c5:04:f0:49:e4:77:9f: fc:1f:6b:b6:f8:1d:3f:c0:3c:12:a5:cb:a1:68:76: 29:76:f8:0c:74:07:58:bf:4f:ba:a6:9f:a4:4b:50: e2:6a:27:5f:4c:c0:94:47:7a:24:53:e5:eb:73:4c: a7:53:7a:a3:0b:b1:60:7f:2a:b9:9a:ed:44:63:20: f0:39:32:cb:36:93:6e:92:c0:05:db:c9:10:ae:32: 8a:2b:df:39:84:28:69:7e:1c:2f:38:b0:a8:c3:e4: 87:af Exponent: 65537 (0x10001) Signature Algorithm: md5WithRSAEncryption88:61:19:2b:74:f0:63:4a:d0:a4:6d:ff:48:5e:b5:01:aa:be: c6:0e:82:c6:53:11:86:b4:78:53:39:d4:0d:58:1d:be:11:47: a2:69:2a:73:aa:06:1f:4e:65:75:46:f3:59:8f:69:73:75:79: 6f:cd:0e:a8:7a:56:b8:5c:02:ff:b6:78:8b:dc:ca:96:3f:2f: 70:21:24:4a:83:ad:d9:bc:b4:88:60:e1:28:ea:9c:7f:0a:c8: b6:d2:08:82:aa:cf:31:01:bd:65:41:95:b6:cb:30:3f:0c:e8: b1:7c:e0:94:d9:4b:69:87:79:d2:c4:e7:3e:51:3e:6a:2e:df: a3:83:84:27:f7:ee:80:fd:c3:28:21:04:c4:46:1b:8b:ff:43: 73:e7:fe:bd:89:3f:0a:1b:2d:6a:57:62:94:2d:46:56:66:1a: 80:a1:07:7a:fe:f6:ff:ce:80:7f:8a:bd:3e:e4:06:41:16:4a: b4:66:bc:07:87:40:5f:26:d1:48:ab:df:ee:6d:f4:6a:b1:07: 83:45:44:c6:6a:26:c6:23:d5:58:c5:9e:1e:f0:32:98:35:07: b1:08:45:ee:77:d5:b9:27:f6:41:ad:08:f6:63:be:3e:63:9e: 62:26:de:6e:8e:1f:e9:9e:29:4f:6f:67:d7:62:cc:f2:ec:e6: b7:e0:0f:66The two certificates you create MUST have the following fields set correctly: • Issuer Common Name: ece422 • Subject Common Name: your RollNumber • Not valid before: March 1, 2017 • Not valid after: March 27, 2017 • Country code: US • State or Province: Illinois • Signature Algorithm: md5WithRSAEncryptionHowever, other fields, such as Subject Pseudonym, are optional and can be set to whatever you desire. You must submit these certificates in the files sol_3.2.4_certA.cer and sol_3.2.4_certB.cer.You must also include the factors for the RSA modulus of the public keys in sol_3.2.4_factorsA.hex and sol_3.2.4_factorsB.hex (one factor per line, as a hexadecimal number). Each individual factor must be a prime numer larger than 256 bits, with the total size of the RSA modulus being at least 2000 bits. The signature from the CS 473 CA must be identical for both certificates. What to submit Your colliding certificates in sol_3.2.4_certA.cer and sol_3.2.4_certB.cer and the RSA factors in sol_3.2.4_factorsA.hex and sol_3.2.4_factorsB.hex.Submission Checklist • sol_3.1.1_decimal.txt • sol_3.1.1_binary.txt • sol_3.1.2.py • sol_3.1.2.txt • sol_3.1.3.py • sol_3.1.3.txt • sol_3.1.4.hex • sol_3.1.5.py • sol_3.1.5.hex • sol_3.1.6.py • sol_3.1.6.txt • sol_3.2.1.py • sol_3.2.1.txt • sol_3.2.2_good.py • sol_3.2.2_evil.py • sol_3.2.3.txt • sol_3.2.3.py • sol_3.2.4_certA.cer • sol_3.2.4_certB.cer • sol_3.2.4_factorsA.hex • sol_3.2.4_factorsB.hex Example content of a .txt solution file # this line is ignored SPN WMKTQIW QR SPBW HQGRSEMW HQVS QY VEKWExample content of a .hex solution file # this line is also ignored 3dab821d92b5ca7f48beee066996b8abc82f7e5646a0561710ea5bc11c80d
This project consists of writing a program that translates logical to physical addresses for a virtual address space of size 2 16 = 65,536 bytes. Your program will read from a file containing logical addresses and, using a page table, will translate each logical address to its corresponding physical address and will output the value of the byte stored at the translated physical address. The goal of this project is to simulate the steps involved in translating logical to physical addresses, using single level paging.Specifics Your program will read a file (addresses.txt) containing several 32-bit integer numbers that represent logical addresses. However, you need only be concerned with 16-bit addresses, so you must mask the rightmost 16 bits of each logical address. These 16 bits are divided into (1) an 8-bit page number and (2) 8-bit page offset. Hence, the addresses are structured as shown in Figure 1. Other specifics include the following: ∙ 2 8 entries in the page table ∙ Page size of 2 8 bytes ∙ Frame size of 2 8 bytes ∙ Physical memory of 16,384 bytes (i.e., 16 KB). 31 16 15 8 7 0 Unused Page number Offset Figure 1. Address structure Additionally, your program need only be concerned with reading logical addresses and translating them to their corresponding physical addresses.You do not need to support writing to the logical address space. Address Translation Your program will translate logical to physical addresses using a page table as outlined in Section 8.5. First, the page number is extracted from the logical address and the page table is consulted to retrieve the frame number for logical to physical address translation. Either the frame number is obtained from the page table, or a page fault occurs if the referenced page is not present in the main memory. Structure of Page Table Entry A page table entry is of two bytes with the following structure: ∙ Bit0 – Bit7 – store the frame number ∙ Bit8 – indicates indicate whether the page is in memory or not. ∙ Bit9 – indicates indicate whether the page is in memory is dirty or not. ∙ Bit10 -Bit11 – are used as 2-bit counter to implement the enhanced second chance algorithm for page replacement as discussed below. Figure 2 shows the structure of page table entry for Part 1. Figure 2.Page table entry structure for Part 1 Page Replacement Strategy Since the logical memory is bigger than the physical memory, you will need to use a page replacement strategy to replace the frames as needed. You have to write the swapped out frame to a backing store file (BACKING_STORE_1.bin), and reload it as needed later on. The strategy that you will use is the enhanced page replacement strategy as described in Section 10.4.5.3 (Enhanced Second Chance Algorithm) in the 10 th edition of the Silberschatz’s Textbook. Handling Page FaultsYour program will implement demand paging as described in Section 10.2 of the textbook. The backing store is represented by the file BACKING_STORE_1.bin, a binary file of size 65,536 bytes. When a page fault occurs, you will read in a 256-byte page from the file BACKING STORE and store it in an available page frame in physical memory. For example, if a logical address with page number 15 resulted in a page fault, your program would read in page 15 from BACKING STORE (remember that pages begin at 0 and are 256 bytes in size) and store it in a page frame in physical memory. Once this frame is stored (and the page table is updated), subsequent accesses to page 15 will be resolved by the page table. You will need to treat BACKING_STORE_1.bin as a random-access file so that you can randomly seek to certain positions of the file for reading. We suggest using the standard C library functions for performing I/O, including fopen(), fread(), fseek(), and fclose(). Test File We provide the file addresses.txt, which contains integer values representing logical addresses ranging from 0 – 65,535 (the size of the virtual address space). Additionally, each address will have a corresponding 0 or 1 written in the same line, representing whether the address is a read or a write.Your program will open this file, read each logical address and translate it to its corresponding physical address. If it is a read, print the signed byte along with the corresponding logical and physical address (see output format below). If the corresponding page is not present in the memory, you need to retrieve it from the BACKING_STORE_1.bin. If it’s a write, you need to first read the byte value at the given address, divide by 2, and write the resulting byte value back to the given memory address. Moreover, you need to print the corresponding logical and physical addresses as well as the resulting byte value after dividing by 2 (see output format below). In addition, the dirty bit in the corresponding page table entry will be set to ‘1’. If the corresponding page is not present in the memory, you need to retrieve it from the BACKING_STORE_1.bin.You also need to update the reference bit in the page replacement strategy as needed. How To Begin First, write a simple program that extracts the page number and offset from the following integer numbers: 1, 256, 32768, 32769, 128, 65534, 33153 Perhaps the easiest way to do this is by using the operators for bit-masking and bit-shifting. Once you can correctly establish the page number and offset from an integer number, you are ready to begin. How To Run Your Program Compile your program by running Makefile: make Your program should run as follows: ./run addresses.txt. Your program will read in the file addresses.txt, which contains 1000 logical addresses ranging from 0 to 65,535. Your program is to translate each logical address to a physical address and determine the contents of the signed byte stored at the correct physical address. (Recall that in the C language, the char data type occupies a byte of storage, so we suggest using char values)Your program is to output the following values: 1. The logical address being translated (the integer value being read from addresses.txt). 2. The corresponding physical address (what your program translates the logical address to). 3. Whether the access was read or write 4. The signed byte value stored at the translated physical address. 5. Whether the access resulted in page fault or not. Output format for both read and write: If upon a read for address 0xFA1C, there’s a page fault and Page number 0xFA is allocated to Frame 0x84, and the data at the logical address 0xFA1C in the backing store is 0x45. print: Logical Address Physical Address Read/Write Value Page Fault 0xFA1C 0x841C Read 0x45 Yes We also provide the file sample.txt, which contains the first 15 sample output values for the file addresses.txt. Statistics After completion, your program is to report the page-fault rate — the percentage of address references that resulted in page faults (i.e. number of page faults divided by the number of memory addresses read).In part 2, you have logical addresses of size 24 bits, and thus the address space is 2 24 bytes (i.e., 16,777,216 bytes) . For any new details not specified in this part, you can assume that they match the requirements defined in Part 1. Address Translation You will use two levels of paging. The first 6 bits will define the offset in the Level 1 page table, the second 8 bits will define the offset in the Level 2 page table, and the final 10 bits will define the offset in the actual frame as shown in Figure 3. Figure3. Address structure for Part 2 Page Replacement and Handling Page faults On top of implementing a double level paging scheme, your physical memory is limited to 128 kilobytes. This means that you can neither keep all Level 2 page table, nor keep all the frames in the memory. Out of 128 kilobytes (128 frames), you can use only 33 frames to store the page tables – 1 frame for storing the ENTIRE Level 1 page table and 32 frames for storing level 2 page table. NOTE: LEVEL 1 Page Table will always be present in memory. Thus, you will need to use a page replacement strategy to replace the frames as needed.Depending on your implementation, you will have page faults in both L1 page table and L2 page table. You may store the remainder of the L2 page table on the backing store below the last instruction you will be processing (next page). The strategy that you will use is the enhanced page replacement strategy as described in Section 10.4.5.3 (Enhanced Second Chance Algorithm) in the 10 th edition of the Silberschatz’s Textbook. Structure of Page Table Entry for Part 2 A page table entry is of 4 bytes with the following structure: ∙ Bit0 – Bit15 – store the frame number ∙ Bit16 – indicates indicate whether the page is in memory or not. ∙ Bit17 – indicates indicate whether the page is in memory is dirty or not. ∙ Bit18 -Bit19 – are used as 2-bit counter to implement the enhanced second chance algorithm for page replacement as discussed below. ∙ Bit20 -Bit31 — are unused. Figure 4 shows the structure of page table entry for Part 2. Figure 4. Page table entry structure forPart 2 Program Execution: You are given a file BACKING_STORE_2.bin (size 16,777,216 bytes). In this file we have placed a binary form of a code (Recall from your CS-225 course that every code you write is first converted to its binary form before execution as computer only understands binary language). This binary code starts at (the first instruction is at) address 0x00C17C00 in BACKING_STORE_2.bin and ends at (the last instruction is at) 0x00C193E8. Your task is to extract this binary from BACKING_STORE_2.bin and execute this binary code using your 2- level paging system.Note: After completion of the program, make sure that you write all the dirty pages back to the backing store. Decoding binary code: In this binary code each instruction is of 8 bytes and each memory address is of 3 bytes. There are only two types of instructions in the binary (memory-memory instructions and memory value instructions). In memory-memory instruction both arguments of the instruction are memory addresses so you need to read the value from both addresses and store the result of the operation in the first memory address. In memory-value instruction, the first argument of the instruction is a memory address and second argument is an immediate value.The result of the operation is to be stored at memory address. As mentioned earlier each instruction is of 8 bytes starting from address 0x00C17C00. The first byte will tell you the op code of the instruction as well as the type of instruction (mem-mem or mem-value). The mapping is given in Table 1 below. Table 1. Instruction mapping table First byte of instruction (Hex) Opcode Instruction type 10 Add memory-value 11 Add memory-memory 20 Mov memory-value 21 Mov memory-memory 30 Sub memory-value 31 Sub memory-memory 40 Multi memory-value 41 Multi memory-memory 50 AND memory-value 51 AND memory-memory 60 OR memory-value 61 OR memory-memory 70 XOR memory-value 71 XOR memory-memory The structure of the instruction is given below. Memory-Memory Instruction structure: Byte7 Byte6 Byte5 Byte4 Byte3 Byte2 Byte1 Byte0 Opcode First Address Second Address Unused Memory-Value Instruction structure: Byte7 Byte6 Byte5 Byte4 Byte3 Byte2 Byte1 Byte0 Opcode First Address Value Note: You have to use memory management system with 2 level page tables to execute this code. The addresses in the instructions are also from BACKING_STORE_2.bin.Example Instruction: For example, if the instruction is 0x601011e211111110, the opcode 60 indicates that the instruction is OR and it is a memory-value instruction. To execute this instruction, you need to read the value at address 0x1011e2 from BACKING_STORE_2.bin let’s call the value A. Take bitwise OR of A with 0x11111110 and store the result of the operation at address 0x1011e2. Expected output: You are required to execute all the binary code instructions from Address 0x00C17C00 to 0x00C193E8. On each instruction you need to print the following: 1. Type of instruction. 2. Whether the memory address access was a page hit or miss for both inner and outer page table. 3. The value at that address. Output format Instructi on Type (memory memory or memory value) Address 1 – Outertab le Page table hit/miss Address 1 – Innerta ble Page table hit/miss Address 2 – Outertab le Page table hit/miss Address 2 – Innerta ble Page table hit/miss Value at Address 1 before executio n Value at Address 1 after executio n Instruction read – opcode, first address, second address/value We also provide the file sample.txt, which contains the first 15 sample output values for the file addresses.txt. Submission Guidelines: You have been provided with a zipped file. The zipped file contains two folders, for part 1 and part 2. DO NOT rename any of the existing files or folders.You can however change the ● Makefiles to add any new code. However, make sure the -o flag of gcc is not changed, and the name of the final executable is run. ● Zip both the folders, without adding them to a new folder, and upload the zipped file to LMS. ● The final zip file must be renamed as _.zip, where R1 and R2 are the roll numbers of the group members. ● Only one member in the group needs to submit the assignment. General Tips (for both parts): This assignment might seem daunting at first but the underlying concepts are not very hard. If you understand the concepts correctly, writing pseudo-code for the whole assignment would not take more than a couple of hours. For implementation, I recommend using a top-down programming approach.Try to use: 1. Global constants (e.g. PAGE_ENTRIES, PAGE_SIZE, MEM_SIZE, DIRTYBIT, COUNTBITS, VALIDBIT etc.). This would make your code cleaner, less error prone, and easier to understand for yourself 2. Modular design. Divide each task into separate procedures. Some obvious functions include functions for getting a free memory location, setting certain bits (dirty, invalid etc), getting a byte from a given address, exporting page, parsing instruction (for part 2), hexadecimal to decimal converter etc. Once you have the pseudo-code written, you’ll then just need to implement each function one by one. Try to test each function as you write it. If you test all of your functions at the end, it would be very hard for you to catch errors.
Question 1: You’ve been hired by XYZ University to build a controller for their elevator system. The university has one elevator that starts from the ground floor and goes to the top floor and then comes back to the ground floor (and so on).You must make a thread for the elevator that will run until there are no more users waiting for the elevator on any of the floors or inside the elevator.You will begin this thread in the start function provided. A user is represented by a thread – when the user gets to the elevator, the user calls “GoingFromTo(int fromFloor, int toFloor)”. The thread should not return until the elevator hasgone from the fromFloor to the toFloor. For simplicity, you can assume the elevator holds only 20 people.Extra Instructions for Help: Think about the problem this way: A user starts when he/she reaches the elevator. All Users wait on a floor until the elevator reaches that floor. The elevator then signals all the waiting users on that floor to get on and all the waiting users inside the elevator that want to get out on that floor. You will find that having two semaphores per floor will help you execute this easily – One for users waiting inside and one for the users waiting outside the elevator. See the part1.h and part1.c for more instructionsQuestion 2: You have been hired by the Metropolitan Transit authority (MTA) to design controller of their automated trains around the city in a circular loop. The stations in this loop are numbered 1 through N. Each station has a boarding area where passengers wait for the train in a queue. To enter the boarding area, passengers need to scan their ticket on an automated machine. Similarly, just before entering the train passengers scan their tickets on a 2nd scanning machine.The scanned information includes the source station and destination station of the passenger. Suppose that the capacity of each train is 50 (i.e., only 50 passengers can be in the train at any given point in time). There are 5 trains running in the loop. When a train arrives at the station passengers waiting in the queue board the train. If the train becomes full, it does not take further passengers and the remaining passengers in the queue wait for the next train.A train stops at a given station only, if any of the following two conditions hold: There are one or more passengers waiting for the train in the boarding area of the given station. There are one or more passengers who need to get off from the train at the given station (i.e., these passengers have declared the given station as their destination station). Each passenger is represented by a thread. The passenger thread shouldn’t exit until the passenger has reached the destination station.Extra Instructions for Help: If you have done part 1, you will realize that you can approach this question in the same way. However, now instead of one medium (Elevator), this time you have 5 mediums (trains). The execution plan remains the same.Question 3 You have been hired by Uber to design the operating systems of their automated cars running in the downtown area. Specifically, Uber has asked you to design a system that enables their cars to safely cross intersections with traffic lights. This system includes a traffic light controller and car controller. As depicted in the Figure below, suppose that all intersections in the given downtown area have traffic lights controlling 4-way traffic.The traffic flow is North-bound, South-bound, East-bond, and West-bound. Each road on the intersection has 4 lanes (2 lanesfor Northbound traffic and 2 lanes for South-bound traffic) or (2 lanes for East-bound traffic and 2 lanes for Westbound traffic). A car arriving at the intersection may go straight, or turn left or right. Following rules need to be followed for crossing the intersection. 1. There are four traffic lights, one for each of the North-bound, South-bound, East-bound, and West-bound Road. Only one traffic light becomes green at any given time; the remaining traffic light will be red. 2. A car going straight or turning left must be in the left lane.3. A car turning right must be in the right lane. 4. A car going straight or turning right cannot cross the intersection if the corresponding traffic light is red and must wait for the traffic light to go green. The traffic light for going straight or turning right becomes green at the same time. 5. A car may turn left on Red light if there is no car waiting in front of it for green traffic light.6. A traffic light remains green until 5 waiting cars from each lane cross the intersection or turn right. In case there are less than 5 waiting cars in each lane, the traffic light becomes red as soon as all the waiting cars cross the intersection or turn right. 7. Each car is represented by a thread. The car thread shouldn’t exit until the car has crossed the intersection or made the turn.Submission Instructions: 1. Please follow the print format as stated in the code files. 2. You only need to submit cpp and header (.h) files for all three questions. There will be total 6 files. 3. Make a zip file containing your submission files and name it A3_.zip where is your roll number e.g A3_22100027.zip
This assignment consists of designing a C program to serve as a shell interface that accepts user commands and then executes each command in a separate process.Your implementation will support input and output redirection, as well as pipes as a means of IPC between a pair of commands. Completing this project will involve using the UNIX fork ( ), exec (), wait ( ), dupe (), and pipe ( ) system calls and can be completed on any Linux, UNIX, or macOS system.A shell interface gives the user a prompt, after which the next command is entered. The example below illustrates the prompt osh> and the user’s next command: cat prog . c. (This command displays the file prog . c in the terminal using the UNIX cat command.) osh›cat prog.cOne technique for implementing a shell interface is to have the parent process first read what the user enters on the command line (in this case, cat prog . c) and then create a separate child process that performs the command. Unless otherwise specified, the parent process waitsfor the child to exit before continuing.However, UNIX shells typically also allow the child process to run in the background, or concurrently. To accomplish thqt, we add an ampersand (&) at the end of the command. Thus, if we rewrite the above command as osh>cat prog.c & the parent and child processes will run concurrently.The separate child process is created using the fork () system call, and the user’s command is executed using one of the system calls in the exec ( ) family. For the purpose of this assignment, we will only be using execvp () system A C program that provides the general operations of a command-line shell is supplied in the figure below.The main ( ) function presents the prompt osh> and outlines the steps to be taken after input from the user has been read. The main () function continually loops as long as should_run equals 1; when the user enters exit at the prompt, your program will set should_run to 0 and terminate. Figure 3.36This assignment is divided into the following parts: 1) Creating a child process and executing commands in the child (15 marks) 2) Providing a history feature (15 marks) 3) Adding support of input and output redirection (20 marks) 4) Creating environment variables, assigning them values and then reading those values. (25 marks) 5) Making the parent and child process communicate via pipes (25 marks)The first task is to modify the main() function in Figure 3.36 so that a child process is forked and executes the command specified by the user. This will require parsing what the user has entered into separate tokens and storing the tokens in an array of character strings (args in Figure 3.36).For example, if the user enters the command ps -ael at the osh> prompt, the values stored in the args array are: args [0] = “ps” args [1] = “-ael” args [2] = NULLThis args array will be passed to the execvp() function, which has the following prototype: execvp (char *command, char *params []).Here, command represents the command to be performed and params stores the parameters to this command. For this project, the execvp (function should be invoked as execvp(args [0], args). Be sure to check whether the user included & to determine whether or not the parent process is to wait for the child to exit.The next task is to modify the shell interface program so that it provides a history feature to allow a user to execute the most recent command by entering !!. For example, if a user enters the command ls -1, she can then execute that command again by entering !! at the prompt. Any command executed in this fashion should be echoed on the user’s screen, and the command should also be placed in the history buffer as the next command.Your program should also manage basic error handling. If there is no recent command in the history, entering !! should result in a message “No commands in history.Your shell should then be modified to support the ‘>’ redirection operators, where ‘>’ redirects the output of a command to a file. For example, if a user enters: osh>ls > out.txtthe output from the ls command will be redirected to the file out.txt. Managing the redirection of output will involve using the dup2() function, which duplicates an existing file descriptor to another file descriptor. For example, if fd is a file descriptor to the file out.txt, the call dup2(fd, STDOUT_FILENO); duplicates fd to standard output (the terminal). This means that any writes to standard output will in fact be sent to the out.txt file. You can assume that commands will contain only one output redirectionAn environment variable is a variable which is a part of the environment in which a process runs. All processes running in the environment are able to access the values of the environment variables within the environment and then use them for different purposes such as performing calculations using their values, storing their values in a file or simply displaying their values on the shell.In this task, we modify our simple shell so that it allows the creation of environment variables and then lets us access them. For simplicity, we will only be displaying the values of our created environment variables on our shell and storing their values in a file. The following command is used to create environment variables within the shell: VAR=hello_worldwhere VAR is the name of the environment variable and hello_world is its value. For simplicity, we will assume that our environment variables can only store values of type string and our program can have only 10 environment variables at max. Since our environment variables can store only string values, we do not need to add quotes around values. Hence, you are only expected to cater to inputs of the above format, without any quotation marks.Once the environment variable has been created, you should be able to access it and print its value. This can be done via the following command: echo $VARThis should display the string literal, hello_world on your terminal. If an environment variable does not exist, the terminal should display NotFound. For example: echo $ABC, should display NotFound.Now that our environment variable is being displayed on the shell, we will use output redirection to store its value in the file. For example echo $VAR > newFile should create a file by the name of newFile and store the literal hello_world in this file. You should be able to verify this by typing the following command: cat newFile This command should display hello_world on the terminal screen.The final modification to your shell is to allow the output of one command to serve as input to another using a pipe. For example, the following command sequence osh>ls -l | less has the output of the command ls -l serve as the input to the less command. Both the ls and less commands will run as separate processes and will communicate using the UNIX pipe () function described in Section 3.7.4.Perhaps the easiest way to create these separate processes is to have the parent process create the child process (which will execute ls -1). This child will also create another child process (which will execute less) and will establish a pipe between itself and the child process it creates.Implementing pipe functionality will also require using the dup2 function as described in the previous section. Finally, although several commands can be chained together using multiple pipes, you can assume that commands will contain only one pipe character and will not be combined with any redirection operators.
In this project, you will learn how to create a kernel module and load it into the Linux kernel. You will then modify the kernel module so that it creates an entry in the /proc file system.The project can be completed using the Linux virtual machine that is available with this text. Although you may use any text editor to write these C programs, you will have to use the terminal application to compile the programs, and you will have to enter commands on the command line to manage the modules in the kernel.As you’ll discover, the advantage of developing kernel modules is that it is a relatively easy method of interacting with the kernel, thus allowing you to write programs that directly invoke kernel functions. It is important for you to keep in mind that you are indeed writing kernel code that directly interacts with the kernel. That normally means that any errors in the code could crash the system! However, since you will be using a virtual machine, any failures will at worst only require rebooting the system.I. Kernel Modules Overview The first part of this project involves following a series of steps for creating and inserting a module into the Linux kernel. You can list all kernel modules that are currently loaded by entering the command lsmod This command will list the current kernel modules in three columns: name, size, and where the module is being used. #include #include #include /* This function is called when the module is loaded. */ int simple init(void) { printk(KERN INFO “Loading Kernel Module∖n”); return 0; } /* This function is called when the module is removed. */ void simple exit(void) { printk(KERN INFO “Removing Kernel Module∖n”); } /* Macros for registering module entry and exit points. */ module init(simple init); module exit(simple exit); MODULE LICENSE(“GPL”); MODULE DESCRIPTION(“Simple Module”); MODULE AUTHOR(“SGG”); Figure 2.21 Kernel module simple.c.The program in Figure 2.21 (named simple.c and available with the source code for this text) illustrates a very basic kernel module that prints appropriate messages when it is loaded and unloaded. The function simple init() is the module entry point, which represents the function that is invoked when the module is loaded into the kernel. Similarly, the simple exit() function is the module exit point— the function that is called when the module is removed from the kernel.The module entry point function must return an integer value, with 0 representing success and any other value representing failure. The module exit point function returns void. Neither the module entry point nor the module exit point is passed any parameters. The two following macros are used for registering the module entry and exit points with the kernel: module init(simple init) module exit(simple exit)Notice in the figure how the module entry and exit point functions make calls to the printk() function. printk() is the kernel equivalent of printf(), but its output is sent to a kernel log buffer whose contents can be read by the dmesg command. One difference between printf() and printk() is that printk() allows us to specify a priority flag, whose values are given in the include file. In this instance, the priority is KERN INFO, which is defined as an informational message.The final lines—MODULE LICENSE(), MODULE DESCRIPTION(), and MODULE AUTHOR()—represent details regarding the software license, description of the module, and author. For our purposes, we do not require this information, but we include it because it is standard practice in developing kernel modules.This kernel module simple.c is compiled using the Makefile accompanying the source code with this project. To compile the module, enter the following on the command line: make The compilation produces several files. The file simple.ko represents the compiled kernel module. The following step illustrates inserting this module into the Linux kernel. II. Loading and Removing Kernel Modules Kernel modules are loaded using the insmod command, which is run as follows: sudo insmod simple.ko To check whether the module has loaded, enter the lsmod command and search for the module simple. Recall that the module entry point is invoked when the module is inserted into the kernel. To check the contents of this message in the kernel log buffer, enter the command dmesgYou should see the message “Loading Module.” Removing the kernel module involves invoking the rmmod command (notice that the .ko suffix is unnecessary): sudo rmmod simpleBe sure to check with the dmesg command to ensure the module has been removed. Because the kernel log buffer can fill up quickly, it often makes sense to clear the buffer periodically. This can be accomplished as follows: sudo dmesg -c Proceed through the steps described above to create the kernel module and to load and unload the module. Be sure to check the contents of the kernel log buffer using dmesg to ensure that you have followed the steps properly.As kernel modules are running within the kernel, it is possible to obtain values and call functions that are available only in the kernel and not to regular user applications. For example, the Linux include file defines several hashing functions for use within the kernel. This file also defines the constant value GOLDEN RATIO PRIME (which is defined as an unsigned long).This value can be printed out as follows: printk(KERN INFO “%lu∖n”, GOLDEN RATIO PRIME); As another example, the include file defines the following function unsigned long gcd(unsigned long a, unsigned b); which returns the greatest common divisor of the parameters a and b.Once you are able to correctly load and unload your module, complete the following additional steps: 1. Print out the value of GOLDEN RATIO PRIME in the simple init() function. 2. Print out the greatest common divisor of 3,300 and 24 in the simple exit() function. As compiler errors are not often helpful when performing kernel development, it is important to compile your program often by running make regularly. Be sure to load and remove the kernel module and check the kernel log buffer using dmesg to ensure that your changes to simple.c are working properly.In Section 1.4.3, we described the role of the timer as well as the timer interrupt handler. In Linux, the rate at which the timer ticks (the tick rate) is the value HZ defined in . The value of HZ determines the frequency of the timer interrupt, and its value varies by machine type and architecture.For example, if the value of HZ is 100, a timer interrupt occurs 100 times per second, or every 10 milliseconds. Additionally, the kernel keeps track of the global variable jiffies, which maintains the number of timer interrupts that have occurred since the system was booted. The jiffies variable is declared in the file .1. Print out the values of jiffies and HZ in the simple init() function. 2. Print out the value of jiffies in the simple exit() function.P-4 Save a screenshot of the dmesg result after inserting and removing simple.ko. Screenshot should be inserted under Part I (simple.c) in the answer_sheet file. The result should contain these statements: “Loading Module”, [Value of golden ratio], [Value of HZ], [Value of jiffies when inserting module], “Removing Module”, [Value of GCD of 3300 and 24], [Value of jiffies at module removal] (perform these steps in simple.c file) (Perform these steps in simple.c file) Run ‘sudo dmesg -c’ before running ‘dmesg’.Chapter 2 Operating-System Structures Before proceeding to the next set of exercises, consider how you can use the different values of jiffies in simple init() and simple exit() to determine the number of seconds that have elapsed since the time the kernel module was loaded and then removed.III. The /proc File System The /proc file system is a “pseudo” file system that exists only in kernel memory and is used primarily for querying various kernel and per-process statistics. #include #include #include #include #include #define BUFFER SIZE 128 #define PROC NAME “hello” ssize t proc read(struct file *file, char user *usr buf, size t count, loff t *pos); static struct file operations proc ops = { .owner = THIS MODULE, .read = proc read, }; /* This function is called when the module is loaded. */ int proc init(void) { /* creates the /proc/hello entry */ proc create(PROC NAME, 0666, NULL, &proc ops); return 0; } /* This function is called when the module is removed. */ void proc exit(void) { /* removes the /proc/hello entry */ remove proc entry(PROC NAME, NULL); } Figure 2.22 The /proc file-system kernel module, Part 1This exercise involves designing kernel modules that create additional entries in the /proc file system involving both kernel statistics and information relatedto specific processes. The entire program is included in Figure 2.22 and Figure 2.23. We begin by describing how to create a new entry in the /proc file system. The following program example (named hello.c and available with the source code for this text) creates a /proc entry named /proc/hello. If a user enters the command cat /proc/hello the infamous Hello World message is returned. /* This function is called each time /proc/hello is read */ ssize t proc read(struct file *file, char user *usr buf, size t count, loff t *pos) { int rv = 0; char buffer[BUFFER SIZE]; static int completed = 0; if (completed) { completed = 0; return 0; } completed = 1; rv = sprintf(buffer, “Hello World∖n”); /* copies kernel space buffer to user space usr buf */ copy to user(usr buf, buffer, rv); return rv; } module init(proc init); module exit(proc exit); MODULE LICENSE(“GPL”); MODULE DESCRIPTION(“Hello Module”); MODULE AUTHOR(“SGG”); Figure 2.23 The /proc file system kernel module, Part 2 In the module entry point proc init(), we create the new /proc/hello entry using the proc create() function. This function is passed proc ops, which contains a reference to a struct file operations. This struct initialP-6 You will need to change the Make file by replacing simple.o with hello.o. Run make again.Chapter 2 Operating-System Structures izes the .owner and .read members. The value of .read is the name of the function proc read() that is to be called whenever /proc/hello is read. Examining this proc read() function, we see that the string “Hello World∖n” is written to the variable buffer where buffer exists in kernel memory. Since /proc/hello can be accessed from user space, we must copy the contents of buffer to user space using the kernel function copy to user().This function copies the contents of kernel memory buffer to the variable usr buf, which exists in user space. Each time the /proc/hello file is read, the proc read() function is called repeatedly until it returns 0, so there must be logic to ensure that this function returns 0 once it has collected the data (in this case, the string “Hello World∖n”) that is to go into the corresponding /proc/hello file. Finally, notice that the /proc/hello file is removed in the module exit point proc exit() using the function remove proc entry().This assignment will involve designing two kernel modules: 1. Design a kernel module that creates a /proc file named /proc/jiffies that reports the current value of jiffies when the /proc/jiffies file is read, such as with the command cat /proc/jiffies Be sure to remove /proc/jiffies when the module is removed.2. Design a kernel module that creates a proc file named /proc/seconds that reports the number of elapsed seconds since the kernel module was loaded. This will involve using the value of jiffies as well as the HZ rate. When a user enters the command cat /proc/seconds your kernel module will report the number of seconds that have elapsed since the kernel module was first loaded. Be sure to remove /proc/seconds when the module is removed.P-7 1. Task ‘jiffies’ should be done in a new file called jiffies.c. It might be a good idea to take starting code from the given hello.c file for this task. After you are done with this task, attach a screenshot of the result under part II (jiffies) of the answer sheet. A sample command structure for the screenshot would look like: sudo dmesg -c, make, sudo insmod jiffies.ko, cat /proc/jiffies, sudo rmmod jiffies, dmesg2. Task ‘seconds’ should be done in a new file called seconds.c. It might be a good idea to take starting code from the given hello.c file for this task. After you are done with this task, attach a screenshot of the result under part III (seconds) of the answer sheet. A sample command structure for the screenshot would look like: sudo dmesg -c, make, sudo insmod seconds.ko, cat /proc/seconds, cat /proc/seconds, cat /proc/seconds, sudo rmmod seconds, dmesgThe answer sheet should be renamed as answers_[roll no].pdf. For example, if your roll number is 21100115, then the file should be named ‘answers_21100115.pdf’. This answer sheet should contain a screenshot from each of the three tasks. Final submission should contain the following files: simple.c, jiffies.c, seconds.c, answers_[roll no].pdf Compress the 4 files as zip. Rename the zipped file as “assignment1_[roll no].zip”. Submit only this zipped file on LMS.
In this assignment, you are required to apply your knowledge of machine learning models to answer the questions in the notebooks given in the folders Part 1 and Part 2. The parts are independent from each other but it is recommended to solve them in order.The assignment will be checked both manually and through automated test cases via otter. Marks Distribution Part Marks Part 1 50 Part 2 50Submission Guidelines ● You should name both notebooks as YourRollNumber_PartNumber.ipynb. (e.g. the rst part should be named as 2XXXXXXX_1.ipynb) ● You must submit a zip folder containing just two notebooks and it must not have any folder or any other le. ● Use the following naming convention for the submission: .zip For example, if your roll number is 22100277, then your zip le name should be: 22100277.zip
This assignment is based on the causal inference(Part 1) and statistical inference(Part 2). Notebooks for both the parts are given in the folders named part 1 and part 2. Both parts are independent of each other so you can solve them in any order.You may test your code using the test cases provided to you. However, there are some hidden test cases as well. Please note that your code must work for both types of tests to get full credit. Hardcoded values will not be awarded any credit. Further details are given in the respective notebooks.Marks Distribution Part 1: 50 Marks Part 2: 50 Marks Submission Guidelines • You should name both notebooks as YourRollNumber_PartNumber.ipynb. (e.g. the first part should be named as 2XXXXXXX_1.ipynb) • You must submit a zip folder containing just two notebooks and it must not have any folder or any other file. • Use the following naming convention for the submission: .zip For example, if your roll number is 22100277, then your zip file name should be: 22100277.zip
In this assignment, you are required to answer the questions in the notebooks given in the folders Part 1 and Part 2. The parts are independent from each other but it is recommended to solve them in order.You may test your code using the test cases provided to you. However, there are some hidden test cases as well. Please note that your code must work for both types of tests to get full credit. Hardcoded values will not be awarded any credit.Further details are given in the respective notebooks. NOTE : Please read carefully the instructions before beginning any question. Marks Distribution Part Marks Part 1 50 Part 2 50 Submission Guidelines ● You should name both notebooks as YourRollNumber_PartNumber.ipynb. (e.g. the rst part should be named as 2XXXXXXX_1.ipynb) ● You must submit a zip folder containing just two notebooks and it must not have any folder or any other le. ● Use the following naming convention for the submission: .zip For example, if your roll number is 22100003, then your zip le name should be: 22100003.zip
In this assignment, you are required to use Pandas library to answer the questions in the notebooks given in the folders Part 1 and Part 2. The parts are independent from each other but it is recommended to solve them in order.You may test your code using the test cases provided to you. However, there are some hidden test cases as well. Please note that your code must work for both types of tests to get full credit. Hardcoded values will not be awarded any credit.Further details are given in the respective notebooks.
Written Part [25] The given table displays different conditions on the basis of which Zafir decides whether he will go to a restaurant for dinner or not. Perform the ID3 algorithm to generate the decision tree which corresponds to the table. Budget Hungry? Restaurant Reviews Goes to restaurant low no bad no high yes bad no medium no good no low no good no low yes bad yes high yes good yes medium yes bad yes medium no bad no high no good yes Coding Part [75] In this part, you will be implementing the ID3 Algorithm in python. We have provided you with a dataset.txt file that you can work on to test your code.Each row’s values in the dataset corresponds to the following: outlook,temperature,humidity,wind,playTennis The values of each attribute are as follows: Hence, if the row is: 0,0,0,0,0 That would mean that the outlook was sunny, temperature was hot, humidity was high, wind was weak, and the person did not play tennis.You have also been provided encodings.txt. The dataset.txt contains integer labels for the string attribute values. And the encodings.txt contains information about which integer maps to which string label (this will be useful for naming the keys of your output tree). You should interpret this file as follows: ● The first row of encodings.txt gives you the name of columns in the dataset.txt. For the first column name is outlook, 2nd one is Temperature, third is Humidity and so on. ● Then the second row gives you label mappings for attributes inside the first column e.g Outlook.The sunny maps to 0, Rainy maps to 1 and Overcast maps to 2. ● The third row gives label mappings for attributes inside 2nd column e.g Temperature. Hot maps to 0, Mild maps to 1, Cool maps to 2 ● Onward rows follow the same pattern. In short each nth row except 1st one gives you labels for (n-1)th column. And each word inside that row maps to i where i is the index of that word in that row and i starts from 0. You need to make a decision tree based on the values given in dataset.txt. You should use the ID3 algorithm to make the tree.Your need to print your tree as a python dictionary. While Outlook Temperature Humidity Wind Plays Tennis Sunny: 0 Hot: 0 High: 0 Weak: 0 No: 0 Rainy: 1 Mild: 1 Normal: 1 Strong: 1 Yes: 1 Overcast: 2 Cool: 2 printing the tree you will need to convert integer labels back to their original string labels using the encodings given in the table above. Your output will look similar to this: Tips You will need to use the numpy library for this assignment. Numpy is very similar to pytorch which you used in your assignment 2. You will find the following numpy functions helpful for this assignment (this list might be non-exhaustive depending on your implementation). ● numpy.loadtxt() ● numpy.where() ● numpy.log2() ● numpy.count_nonzero() We have pretty-printed the dictionary using the pprint.pprint() function from the builtin python pprint library.You should also do this otherwise your dictionary will be printed in a single line and will be difficult to read. Since your program should be general enough to work on any given dataset of the format described above with a yes/no output, you should consider making datasets yourself to test your code further. It will only take a couple of minutes to make the dataset (the one we have provided is from the example given in class).How to run your code Your data set should be present in the same directory as the python file, and your program should take as input the data set file from the command line. The command to run the program will be as follows: python3 .py .txt .txt (look up sys.argv on the internet to see how you can get the file name from the command line into your program)
Part 1 (theory): Question 1: [25 marks, 5 marks each] The search algorithms you have learnt in CS-331 can be used to traverse the graph shown in Fig 1.1. As you may already know, traversal from each algorithm will result into a different tree. Figure 1.1 was traversed using 7 different search algorithms, and the corresponding tree (R1 to R7) for each algorithm has been given below. In each of the 7 diagrams, where applicable, the cost calculated by that algorithm for each node visited is given next to it. Please note that the children of each node were traversed in an alphabetical fashion.A tabular depiction of the Heuristic functions used for some of the traversals is given in Fig 1.2. To help you correctly interpret Fig 1.2, I will interpret the first row of the table for you. The first row means that H1(A)=3 and H2(A)=3, where H1 and H2 are the two heuristic functions used.Your job is to find out for each tree diagram (R1 to R7) the search algorithm that was used to generate it. Mention whether or not the path generated is optimal (by showing that a path with lesser total cost exists or not) and whether or not any heuristic function (H1 or H2 and why do you think so?) was used.You are required to select one of the following algorithms for each tree: 1. Depth FS 2. Uniform Cost Search 3. Best FS (greedy) 4. A* 5. Breadth FS Fig 1.1 Fig 1.2 R1 R2 R3 R4 R5 R6 R7Question 2: [20 marks, 5 marks each] Use search algorithms #1, #3, #4 and #5 mentioned in Question 1 to write down the ordered list(s) of visited nodes of the tree shown in Fig 2.1 for each of them.Question 3: [20 marks, 4 marks each] This question has several parts: i. Briefly compare Breadth-First Search (BFS) and Depth First Search (DFS). ii. What issue does Depth limited Search resolve? iii. Precisely describe A* search Algorithm. iv. How does uniform cost search differ from A* search? v. Which of the four algorithms mentioned so far are complete? Which ones are optimal?Question 1: [85 marks, 15 marks each for A* search and recursive algorithms, 10 marks for each of the rest] In this part, you are required to implement the famous game Pacman with the help of the search algorithms you have learnt in class. All files for this part have been uploaded on LMS. You are required to edit the skeleton-code given in “search.py” using any text-editor of your choice (Sublime is recommended). An auto-grader for each question is given in “Pacman.ipynb”, which can be executed using Jupyter. Please do not edit the code in any of the other files. *** Z The goal node is Z! If the heuristic of a node is not given, assume it is zero! Fig 2.1
