Maze generation and solving:

• Hai, Zhou, Maze Router: Lee Algorithm
  • These slides from Northwestern University give a great overview of maze routing algorithms. They discuss Lee algorithm, Handlock’s algorithm, Soukup’s algorithm, and more, along with their strengths and weaknesses, and runtime comparisons. This will be a useful resource to learn a little bit about various approaches and narrow down a few I might be interested in implementing.
    • Provides time and space complexity of different approaches presented
    • Some insights on ways to reduce the running time
    • Compares algorithms based on whether each of them is always able to find a path, whether the path found is the shortest, and whether the algorithm works on both grids and lines
    • Introduces some ideas about multi-layered routing

• Xiao Cui, Hao Shi, A*-based Pathfinding in Modern Computer Games, IJCSNS International Journal of Computer Science and Network Security, VOL.11 No.1, January 2011
  • This publication mainly focuses on A* based pathfinding in video games. According to the paper, this algorithm provides a provably optimal solution to pathfinding and has succeeded Dijkstra’s algorithm, BFS, DFS, and others. It explains how the algorithm works and shows the various implementation and optimization techniques. I believe the analysis of the latter will be most useful for the project I have in mind since I would like to look into the running speed/ memory consumption of maze-solving tools.
    • Provides optimization ideas for A* algorithm
    • Provides negative aspects of A*, including the huge amount of memory it requires to run
    • Describes some common applications of the algorithm and how it’s used to solve tricky problems

• Geethu Elizebeth Mathew, Direction Based Heuristic for Pathfinding in Video Games, Procedia Computer Science   47  (2015)  262 – 271
  • This paper reviews current widely used pathfinding algorithms including A* and Dijkstra’s algorithm and proposes a new method, that the author claims to be more optimal than others. The method is based on direction heuristics, which ensures that parts of the map that are irrelevant remain unsearched. I find the approach extremely interesting and would like to explore some weaknesses it might have in more detail.
    • This approach doesn’t care too much about whether a path is the shortest mathematically, as long as it’s virtually short enough
    • The algorithm will only work in a grid-based environment as most of the game worlds are divided into grids for simplicity
    • The method focuses on reducing the resources used in the process as much as possible
    • Compares the behavior of the algorithm to other algorithms

• Semuil Tjiharjadi, Marvin Chandra Wijaya, Optimization Maze Robot Using A* and Flood Fill Algorithm, Erwin Setiawan Maranatha Christian University, Bandung, Indonesia, International Journal of Mechanical Engineering and Robotics Research Vol. 6, No. 5, September 2017 
  • This paper expands on the usage of A* and Flood Fill algorithms in robotics. It discusses the hardware design of a robot created to solve a 3-dimensional maze, as well as testing results of both A* and the Flood Fill algorithm. This paper caught my curiosity since I am really interested in robotics as well, so I would love to recreate some of these tests and compare them to the approach discussed in the previous paper (direction heuristics-based method)
    • Based on the testing results, the size of the maze used in this research (5 x 5) was not sufficient enough to compare the differences between A* and the Flood Fill algorithm
    • Using a wider area is recommended for more accurate results and the distinction between methods, however, it may lead to other run-time-related complications, since as we know A* algorithm requires a lot of memory.

• Walter D. Pullen, Maze Classification, astrolog.org, last updated March 22, 2021
  • This publication gives a great overview of a large list of maze creation and solving algorithms, along with some analysis and comparisons. Just like my source #1, I would like to use it to look deeper into some approaches and narrow down my options for maze generation, as well as solving.
    • Provides a large list of maze classifications based on dimension, hyperdimension, topology, routing, focus, and others
    • Provides possible maze generation and solving algorithms for each of the different types of mazes mentioned above

• Jamis Buck, HTML 5 Presentation with Demos of Maze generation Algorithms
  • These slides explain how mazes work as spanning trees and how they are generated in fairly simple terms. It gives an overview of different types of mazes involving some graph theory and talks about generating spanning trees without bias comparing two different algorithms. I found this publication to be especially useful to deepen my understanding of mazes before I can work on more complex problems in this area.
    • Discussing mazes as spanning trees and comparing 3 different algorithms to create a uniform spanning tree
    • Interactive interface to help get a deeper understanding of each of these algorithms
    • Distinguishes between biased and unbiased mazes and provides algorithms for generating both
      • It seems that generating a biased maze is much faster

• Rosetta Code, Implementations of DFS maze creation algorithm in multiple languages and Implementations of DFS maze solving algorithm in multiple languages, Last modified on 8 January 2022
  • The first article shows a DFS implementation of maze generation in various different programming languages. The second one shows a DFS solution to a maze. I would like to analyze these codes and possibly compare them to other approaches or find ways to optimize them.

Web application security:

• Patrick Engebretson, The Basics of Hacking and Penetration Testing: Ethical Hacking and Penetration Testing, Second Edition, 2013, 2011, Elsevier Inc.
  • This book focuses on ethical hacking and penetration testing. So far I’ve looked into chapters 1, 6, and 7 since I believe these are the most relevant to my area of interest. Chapter 1 introduces Kali Linux, a digital forensics and penetration testing tool I have used before, however, it also provides additional approaches and ideas I have not considered. Chapters 6 and 7 focus on the basics of web hacking including injection attacks that I want to focus on. What I like the most about this resource is that it gives examples, ways to practice, as well as possible applications.
    • Introduces various tools with tutorials on how to use them 
    • Has the structure of a textbook and is easy to follow
    • This is a great source for definitions and ethical hacking practice

• Philipp Vogt, Florian Nentwich, Nenad Jovanovic, Engin Kirda, Christopher Kruegel, Giovanni Vigna, Cross-Site Scripting Prevention with Dynamic Data Tainting and Static Analysis, Secure Systems Lab Technical University Vienna
  • This article introduces a cross-site scripting prevention method using dynamic data tainting and static analysis. Part 3 of the article explains how the method works and offers some implementation approaches. I believe it will be a valuable addition to my web application security tool since one of the main goals of this project will be analyzing and comparing various attacks and their prevention mechanisms.
    • Includes discussion on both, server-side protection and client-side protection
    • It provides Static, as well as Dynamic data tainting analysis and compares their behaviors in terms of advantages and disadvantages, which will be useful to consider in my implementation

• Hassanshahi B., Jia Y., Yap R.H.C., Saxena P., Liang Z. (2015) Web-to-Application Injection Attacks on Android: Characterization and Detection. In: Pernul G., Y A Ryan P., Weippl E. (eds) Computer Security — ESORICS 2015. ESORICS 2015. Lecture Notes in Computer Science, vol 9327. Springer, Cham. 
  • This article focuses specifically on web-to-app injection attacks for Android devices and presents a W2AI (web-to-app injection) scanner mechanism that detects vulnerabilities. This article provides lots of new information about web application hacking on android systems and how they differ from other systems, as well as examples of injection attacks and categorizes various W2AI vulnerabilities. From part 3 on, we learn about how the mechanism works starting from identifying a problem, to solving it and evaluating the results. Despite the fact that I was not initially planning to narrow down to android system web application security at first, given the fact that this is an extremely interesting yet underexplored area, I believe it might be a good focus opportunity for this project.

• William G.J. Halfond, Jeremy Viegas, and Alessandro Orso, A Classification of SQL Injection Attacks and Countermeasures, College of Computing Georgia Institute of Technology

• This article classifies SQL injection attacks and provides some countermeasures. Part 2 introduces some injection mechanisms and application examples, that I believe would be useful for ethical hacking tests, while part 5 shows prevention mechanisms. Unlike other sources I have looked into, this article discusses not only preventing data theft after detecting the attack, but also provides some defensive coding practices including input type checking, encoding of inputs, positive pattern matching and others, which I believe will be extremely useful in creating a secure web-application. 

• Stephen W. Boyd and Angelos D. Keromytis, SQLrand: Preventing SQL Injection Attacks, Department of Computer Science Columbia University

• This publication focuses specifically on preventing SQL injection attacks. Unlike other sources, this one seems to be the closest to what I had in mind for this project. The author starts off by writing a simple CGI application which allows the user to inject SQL into a “where” clause that expected an account ID. Without any validation, the user will be able to retrieve information concerning all possible accounts. Later they introduce a solution using Instruction-Set Randomization, describe its strengths and weaknesses and evaluate its performance. I believe this article gave me a more in-depth understanding of of possible risks and challenges associated with my project, and can be used as a guide for structuring my approach.
• Justin Clarke, SQL Injection Attacks and Defense, 2012, Elsevier, Inc.

• This book focuses on SQL injection attacks and defense. It gives a broader understanding of what a SQL injection is and provides examples of incorrect handling that may lead to exposing a vulnerability in a web application. I looked into Chapters 1, 3 and 4, since they seemed most relevant to my area of interest. They provide examples of dangerous coding behaviors and various ways to analyze code, as well as common exploit techniques. This book provides very broad and detailed information about various aspects in SQL injection in general, and I think it will be a useful resource whenever I feel lost or confused about some specific ideas in this area.

• Jesse Burns, Cross-Site Request Forgery, ©2005, 2007, Information Security Partners, LLC. https://www.isecpartners.com Version 1.2

• This article introduces Cross-Site Request Forgery. While similar to Cross-Site scripting, it’s a separate security risk, and this publication describes some differences between the two. The final part of the article introduces 5 different protection approaches, along with their advantages and disadvantages. While CSRF is not the main focus of my project, given it is closely related to XSS, I would like to explore it if time permits and this article gives me a great understanding of some basic CSRF attacks and preventing mechanisms.

• I want to create a tool that will protect a web application from malicious attacks. As a start, I would like to build a simple website where multiple users are able to sign up, authenticate and store information. Then, I will attempt ethical hacking using injection attacks, like cross-site scripting (XSS) and SQL injection (SQLi). If time permits, I will also explore URL manipulation, session-based attacks, cross-site request forgery, cookie highjacking. As a result, I will discover possible threats and vulnerabilities and improve data encryption, authorization, and access control.
• I want to write software that will generate an n x n or an n x m maze, and find a way out of it. The maze will be represented as a binary matrix where 0 and 1 indicate whether a certain block can be used or not. At the same time, I would also like to analyze differences in memory consumption and runtime between cases where we are able to move in all four directions or only certain directions. 
• I plan to work on a Japanese natural language processing tool. Japanese language, unlike many others, does not use any spacing between meaningful parts of the sentence. Using this application, I hope to help improve the language learning process for students. Since I have already done some work in this area, I have a working piece of software that successfully separates words, however, there still are some mistakes and inconsistencies. I want to improve the existing code and add more features, like a user-friendly interface, displaying word translations (using an external dictionary), parts of speech, and different readings. At the same time, I would like to provide an estimate of the reader’s language comprehension level. I have collected some datasets using web-scraping from an online dictionary (jisho.org), which I plan to use for this project.