Asee peer logo

Don’t Be A Brute: A Programming Assignment For Exposing Undergraduate Students To Computational Complexity And Heuristic Problem Solving Approaches

Download Paper |

Conference

2003 Annual Conference

Location

Nashville, Tennessee

Publication Date

June 22, 2003

Start Date

June 22, 2003

End Date

June 25, 2003

ISSN

2153-5965

Conference Session

Programming and DSP Issues in Education

Page Count

3

Page Numbers

8.452.1 - 8.452.3

Permanent URL

https://peer.asee.org/12666

Download Count

7

Request a correction

Paper Authors

author page

Stephen Yau

Download Paper |

Abstract
NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

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. https://peer.asee.org/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