Nashville, Tennessee
June 22, 2003
June 22, 2003
June 25, 2003
2153-5965
3
8.452.1 - 8.452.3
10.18260/1-2--12666
https://strategy.asee.org/12666
329
Session ______
Don’t be a Brute: A Programming Assignment for Exposing Undergraduate Students to Computational Complexity and Heuristic Problem-Solving Approaches
Tom Wulf
College of Applied Science, University of Cincinnati
Abstract:
A programming assignment that was developed for an undergraduate course in computer security in which students simulate a brute force password guessing attack is described. This exercise helps students to understand issues of computability, re-enforces the basic mathematics of combinatorics, and provides a springboard for discussions of heuristic versus brute-force problem- solving approaches. In the context of a course on computer security, the assignment serves to tangibly demonstrate issues with password selection and user policies that apply to this issue.
Undergraduate students in Computer Science Technology and Information Engineering Technology do not receive the same training in the formal analysis of algorithms that students in standard theory based Computer Science programs do. It is clear, however, that IT students must develop a basic understanding of problem complexity issues and heuristic problem solving approaches to be successful in their careers. The exercise described in this paper gives students a hands-on feel for computational complexity through a programming assignment which simulates a brute-force, password-guessing attack.
Preliminaries: Class Lecture and Readings
In class lecture and assigned readings, students were first introduced to a brute-force password guessing approach in which every possible password string using a finite symbol set for strings of a specified length or range of lengths is generated. Testing for the actual password string then is simply an exhaustive linear search through this generated set. The first issue required in order to examine the magnitude of this task is to determine the cardinality of the set to be tested. This provides an opportunity to review the multiplication rule for the cardinality of permutation sets with the students. A hypothetical operating system that restricts the user to choose password strings of length 8 from the symbol set consisting of the uppercase letters is described and the cardinality of this password set is calculated as an example.
The next step is to consider real world operating systems which allow password strings composed Proceedings of the 2003 American Society for Engineering Education Annual Conference & Exposition Copyright © 2003, American Society for Engineering Education
Yau, S. (2003, June), Don’t Be A Brute: A Programming Assignment For Exposing Undergraduate Students To Computational Complexity And Heuristic Problem Solving Approaches Paper presented at 2003 Annual Conference, Nashville, Tennessee. 10.18260/1-2--12666
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2003 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015