Formal Verification in OS Memory Management
Created byJonas M
2 views0 downloads

Formal Verification in OS Memory Management

College/UniversityMathComputer Science5 days
This project-based learning experience focuses on teaching college-level students how to apply formal methods to verify the reliability and efficiency of operating systems' memory management. Through a series of activities, including logic modeling, finite state machine construction, and vulnerability analysis, students will learn to use propositional and predicate logic, automatons, and formal languages for OS verification tasks. The project aims to improve students' understanding of formal methods, enabling them to identify and resolve potential system vulnerabilities and enhance overall OS efficiency and reliability.
Formal MethodsOperating SystemsMemory ManagementLogicAutomatonsVerificationVulnerabilities
Want to create your own PBL Recipe?Use our AI-powered tools to design engaging project-based learning experiences for your students.
📝

Inquiry Framework

Question Framework

Driving Question

The overarching question that guides the entire project.How can we apply formal methods to verify the reliability and efficiency of operating systems' memory management, using the concepts of logic, automatons, formal languages, and specification?

Essential Questions

Supporting questions that break down major concepts.
  • How can propositional and predicate logic be applied to the verification of operating systems, particularly in the context of memory management?
  • What role do automatons and formal languages play in the specification and verification of an operating system's memory management system?
  • How can formal modelling and specification contribute to identifying and resolving potential vulnerabilities in operating systems?
  • In what ways do formal methods enhance the reliability and efficiency of memory management in operating systems?
  • How are concepts learned in formal methods applied specifically to the development, specification, and verification of software systems?

Standards & Learning Goals

Learning Goals

By the end of this project, students will be able to:
  • Apply formal modelling and specification techniques to verify and improve the reliability and efficiency of operating systems' memory management.
  • Use formal logic, including propositional and predicate logic, to verify the correctness of memory management algorithms in operating systems.
  • Understand and employ automatons and formal languages to aid in the specification and verification of memory management.
  • Identify and address potential vulnerabilities in operating systems through the use of formal methods.
  • Apply knowledge from formal methods courses to practical scenarios in operating system memory management.

CSTA K-12 Computer Science Standards

CSTA-3A-NC-5
Primary
Students design and evaluate computational models and simulations to solve complex problems with and without the assistance of models/simulations and present opportunities for community advocacy or economic activity.Reason: The project requires designing and evaluating models for verifying operating system memory management, relating to computational simulations and problem-solving in computer science.

ABET CS Outcomes

ABET-c
Primary
An ability to design, implement and evaluate a computer-based system, process, component, or program to meet desired needs, using the techniques, skills, and modern engineering tools necessary for computer science practice.Reason: The project involves designing and implementing computer-based verification systems for OS memory management.

Common Core State Standards for Mathematics

CCSS.MATH.PIR
Supporting
Understand and apply the concepts of propositional and predicate logic for specification and verification tasks.Reason: Learning logic for the sake of applying it to OS memory management aligns with these mathematics standards.

Entry Events

Events that will be used to introduce the project to students

Hackathon Challenge: Fix the Bug

Launch a simulation where students are challenged to 'hack' into a system with buggy memory management. As they exploit weaknesses and observe flaws, they embark on a mission to correct these issues using their knowledge of formal methods.
📚

Portfolio Activities

Portfolio Activities

These activities progressively build towards your learning goals, with each submission contributing to the student's final portfolio.
Activity 1

Logic Play for OS Verification

In this activity, students will use their knowledge of propositional and predicate logic to create logical expressions representing memory management processes within operating systems. They will learn how to apply these concepts for verifying system behaviors and identifying flaws.

Steps

Here is some basic scaffolding to help students complete the activity.
1. Review propositional and predicate logic concepts covered in previous courses.
2. Choose a memory management process (e.g., paging, segmentation) to create a logical model for.
3. Formulate logical expressions representing the selected process, stating assumptions and goals.
4. Simulate logical expressions to verify accuracy and identify potential inconsistencies.

Final Product

What students will submit as the final product of the activityLogical models representing memory management processes with verified accuracy.

Alignment

How this activity aligns with the learning objectives & standardsAligns with CCSS.MATH.PIR standards as students apply propositional and predicate logic to verification tasks.
Activity 2

Automaton Builders for Memory Specs

Students will delve into the role of automatons and formal languages by building finite state machines (FSMs) that model memory management algorithms. This activity bridges theoretical concepts with practical system specifications.

Steps

Here is some basic scaffolding to help students complete the activity.
1. Review concepts of automatons and formal languages from previous courses.
2. Select a memory management algorithm to model using FSMs.
3. Design a finite state machine representing states and transitions within the algorithm.
4. Perform simulations of the FSM to validate its functionality against real-world algorithm scenarios.

Final Product

What students will submit as the final product of the activityA finite state machine model accurately representing a memory management algorithm, with validated transitions and states.

Alignment

How this activity aligns with the learning objectives & standardsSupports ABET-c standards by requiring design and evaluation of system components using engineering techniques.
Activity 3

Formal Methods Detective

In this investigative task, students will apply formal modelling techniques to identify potential vulnerabilities in an OS's memory management. Using formal methods, they will specify and verify solutions to these vulnerabilities.

Steps

Here is some basic scaffolding to help students complete the activity.
1. Select a known OS memory management vulnerability.
2. Use formal methods to model the vulnerability and propose potential solutions.
3. Validate proposed solutions using formal verification techniques.
4. Prepare a report detailing the findings and the verification process.

Final Product

What students will submit as the final product of the activityA comprehensive report showcasing identified vulnerabilities, proposed solutions, and their formal verification.

Alignment

How this activity aligns with the learning objectives & standardsFits CSTA-3A-NC-5 by applying computational models and simulations to solve complex OS memory management problems.
Activity 4

Software Specification Savvy

Students will combine all concepts learned to design and implement a full specification for an OS memory management system. They will use formal methods to ensure its reliability and efficiency, creating a complete verification plan.

Steps

Here is some basic scaffolding to help students complete the activity.
1. Consolidate knowledge of logic, automatons, and specification techniques.
2. Draft a full specification for a chosen memory management system, integrating prior learning.
3. Implement formal verification methods to evaluate the specification's reliability and efficiency.
4. Iterate the specification based on formal verification results, optimizing for efficiency.
5. Finalize and document the entire specification and verification process.

Final Product

What students will submit as the final product of the activityA complete, verified specification for an OS memory management system, documented for real-world application.

Alignment

How this activity aligns with the learning objectives & standardsMeets ABET-c standards by designing, implementing, and verifying a computer-based system to meet desired needs.
🏆

Rubric & Reflection

Portfolio Rubric

Grading criteria for assessing the overall project portfolio

Formal Verification of OS Memory Management Assessment Rubric

Category 1

Understanding and Application of Formal Logic

Evaluates the student's comprehension and practical application of logic in memory management verification.
Criterion 1

Conceptual Understanding

Measures understanding of propositional and predicate logic in context of OS processes.

Exemplary
4 Points

Demonstrates a sophisticated understanding of logic principles, with innovative applications.

Proficient
3 Points

Shows thorough understanding and appropriate application of logic concepts.

Developing
2 Points

Exhibits emerging understanding with some inconsistencies in application.

Beginning
1 Points

Shows minimal understanding and struggles with applying logic concepts.

Criterion 2

Logical Expression Development

Assesses ability to develop and simulate logical expressions for OS processes.

Exemplary
4 Points

Creates highly accurate and innovative logical expressions, successfully identifying inconsistencies.

Proficient
3 Points

Develops accurate logical expressions and identifies inconsistencies effectively.

Developing
2 Points

Logical expressions are somewhat accurate with limited error identification.

Beginning
1 Points

Struggles to develop accurate logical expressions and identify errors.

Category 2

Modeling with Automatons and Formal Languages

Assesses the student's capability to use FSMs for modeling memory management algorithms.
Criterion 1

Modeling Techniques

Evaluates design and simulation of finite state machines for memory management.

Exemplary
4 Points

Designs innovative and precise FSMs, successfully simulating real-world scenarios.

Proficient
3 Points

Creates effective FSMs with clear, accurate simulations of algorithms.

Developing
2 Points

FSM models are somewhat accurate but lack thorough simulation.

Beginning
1 Points

FSMs demonstrate limited accuracy and simulation effectiveness.

Criterion 2

Integration of Formal Languages

Assesses application of formal languages in FSM and system specification.

Exemplary
4 Points

Exemplary use of formal languages with innovative integration into FSMs.

Proficient
3 Points

Effectively integrates formal languages into system specifications and FSMs.

Developing
2 Points

Shows basic integration of formal languages with some inconsistencies.

Beginning
1 Points

Lacks effective integration of formal languages into models and specifications.

Category 3

Identification and Resolution of OS Vulnerabilities

Evaluates the identification of vulnerabilities and formulation of verified solutions using formal methods.
Criterion 1

Vulnerability Analysis

Measures ability to identify and model vulnerabilities within OS memory management.

Exemplary
4 Points

Identifies vulnerabilities with exceptional insight and accuracy, proposing innovative solutions.

Proficient
3 Points

Effectively identifies vulnerabilities and proposes viable solutions.

Developing
2 Points

Identifies some vulnerabilities with limited solution proposals.

Beginning
1 Points

Struggles to identify vulnerabilities or propose viable solutions.

Criterion 2

Verification Techniques

Evaluates use of formal verification methods to validate proposed solutions.

Exemplary
4 Points

Employs advanced verification techniques resulting in thoroughly validated solutions.

Proficient
3 Points

Uses appropriate verification methods to confirm solution effectiveness.

Developing
2 Points

Verification approaches are basic with some validation of solutions.

Beginning
1 Points

Utilizes limited verification techniques with minimal solution validation.

Category 4

Comprehensive Specification and Documentation

Assesses ability to produce a complete, verified specification and document the process.
Criterion 1

Specification Quality

Measures completeness and accuracy of system specifications for OS memory management.

Exemplary
4 Points

Produces comprehensive and highly accurate specifications, fully verified for reliability.

Proficient
3 Points

Creates complete and accurate specifications with effective verification process.

Developing
2 Points

Specifications are somewhat complete with partial verification acknowledged.

Beginning
1 Points

Produces incomplete specifications with minimal verification impact.

Criterion 2

Process Documentation

Assesses detailed documentation of specification and verification process.

Exemplary
4 Points

Documents process thoroughly, providing clear insights and reflections.

Proficient
3 Points

Provides detailed documentation with useful insights into verification steps.

Developing
2 Points

Documentation lacks depth and occasional clarity in process details.

Beginning
1 Points

Offers minimal documentation lacking substantial process details.

Reflection Prompts

End-of-project reflection questions to get students to think about their learning
Question 1

Reflect on how your understanding of propositional and predicate logic has evolved through this project. How confident do you feel applying these concepts to real-world OS memory management verification?

Text
Required
Question 2

On a scale from 1 to 5, how effective do you think the formal methods you learned were in solving memory management vulnerabilities?

Scale
Required
Question 3

Which part of the automaton and formal languages activity was most challenging for you, and how did you overcome this challenge?

Text
Optional
Question 4

In the 'Software Specification Savvy' activity, what new insight did you gain about the importance of formal specification in software development?

Multiple choice
Required
Options
It provides a clear framework for system development
It uncovers hidden flaws early in the process
It requires extensive time and effort with high rewards
It enhances overall system reliability
Question 5

To what extent do you agree with the statement: 'Formal methods have significantly improved my ability to identify and resolve OS vulnerabilities.'?

Scale
Required