Answers vary, as you can pick your own videos.
For C, we have to do all memory allocation and deallocation ourselves. We even have to allocate and deallocate each element of the stack ourselves, since “strings” in C have to be managed by the programmer. We have to do defensive copying of these things.
The one thing that is nice about C is that realloc is a nice function from the standard library.
Security features:
realloc to simplify rather than a three-step malloc/copy/free; simplcity is a friend of security.malloc and realloc are checked every single time.// A module for an expandable array-based stack of strings, built from
// scratch. This module is hyper-focused on software security, so you
// will see defensive copying, strict bounds-checking, input validation,
// and error objects prominently featured. Although the stack will grow
// and shrink as necessary, it will never exceed a really big maximum
// capacity. This is to prevent a malicious user from causing the stack
// to grow to an enormous size and consume all available memory.
// Not needed for C23, but needed for C17 and below.
#include <stdbool.h>
#define MAX_CAPACITY 1048576
#define MAX_ELEMENT_BYTE_SIZE 256
// Make the representation of the stack unknown to code that uses it
typedef struct _Stack* stack;
typedef enum {
success,
illegal_stack_capacity,
out_of_memory,
stack_element_too_large,
stack_full,
stack_empty
} response_code;
// Result object for operations returning a stack. If the stack was
// created, the error field will be success and the result will hold
// a pointer to the stack that the caller is responsible for freeing.
// If there is an error, the stack field will be NULL.
typedef struct {
response_code code;
stack stack;
} stack_response;
// Result object for operations returning a string. If the operation
// was successful, the error field will be success and the result will
// hold a pointer to the string that the caller is responsible for freeing.
// If there is an error, the string field will be NULL.
typedef struct {
response_code code;
char* string;
} string_response;
// Note that since stacks are large, we always pass pointers to them.
// But some of the operations do not mutate the stack, so we mark the
// parameter const. Remember that the typedef 'stack' is a pointer type!
// Also the strings themselves are defensively copied in and out of the
// stack.
stack_response create(); // Must destroy() returned stack
int size(const stack s);
bool is_empty(const stack s);
bool is_full(const stack s);
response_code push(stack s, char* item); // Stores copy of string inside stack
string_response pop(stack s); // Will include a copy of the string
// from the stack, so the caller is
// responsible for freeing it
void destroy(stack* s); // frees all the memory for you
#include "expandablestack.h"
#include <string.h>
#include <stdlib.h>
#include <math.h>
const int INITIAL_CAPACITY = 16;
struct _Stack {
char** elements; // array of strings
int capacity; // can grow and shrink
int top; // index of next slot to fill, also the size
};
stack_response create() {
stack s = malloc(sizeof(struct _Stack));
if (s == NULL) {
return (stack_response){out_of_memory, NULL};
}
s->capacity = INITIAL_CAPACITY;
s->top = 0;
s->elements = malloc(INITIAL_CAPACITY * sizeof(char*));
if (s->elements == NULL) {
return (stack_response){out_of_memory, NULL};
}
return (stack_response){success, s};
}
int size(const stack s) {
return s->top;
}
bool is_empty(const stack s) {
return s->top == 0;
}
bool is_full(const stack s) {
return s->top == MAX_CAPACITY;
}
response_code push(stack s, char* item) {
if (is_full(s)) {
return stack_full;
}
if (s->top == s->capacity) {
// Double the array size, but don't exceed the max capacity
int new_capacity = s->capacity * 2;
if (new_capacity > MAX_CAPACITY) {
new_capacity = MAX_CAPACITY;
}
char** new_elements = realloc(s->elements, new_capacity * sizeof(char*));
if (new_elements == NULL) {
return out_of_memory;
}
s->elements = new_elements;
s->capacity = new_capacity;
}
// Not too many folks know about strnlen, but it's great.
size_t item_length = strnlen(item, MAX_ELEMENT_BYTE_SIZE + 1);
if (item_length > MAX_ELEMENT_BYTE_SIZE) {
return stack_element_too_large;
}
// Defensive copy! The stack is going to own a new copy of the
// string, so that the caller can not manipulate the stack contents
// through a back door. It is safe to use strdup here since we
// previously checked its length.
s->elements[s->top++] = strdup(item);
return success;
}
string_response pop(stack s) {
if (is_empty(s)) {
return (string_response){stack_empty, NULL};
}
char* popped_value = s->elements[--s->top];
// Unhook the string from the stack because the "owner" of the string's
// memory is going to be the response object. Do we really have to do this?
// It's good practice!
s->elements[s->top] = NULL;
if (s->top < s->capacity / 4) {
// Shrink the array, but don't go below the initial capacity
int new_capacity = s->capacity / 2;
if (new_capacity < INITIAL_CAPACITY) {
new_capacity = INITIAL_CAPACITY;
}
char** new_elements = realloc(s->elements, new_capacity * sizeof(char*));
if (new_elements == NULL) {
return (string_response){out_of_memory, NULL};
}
s->elements = new_elements;
s->capacity = new_capacity;
}
return (string_response){success, popped_value};
}
void destroy(stack* s) {
// Both the array and the stack itself were malloc'd
free((*s)->elements);
free(*s);
*s = NULL;
}
For C++, you were asked to build this with smart pointers. In real life you might use a vector but it is good to have practice with smart pointers.
One thing that is nice is we can use std::string, which has value semantics, so we can a fair amount of work over C, since there’s no management of memory for strings an no defensive copying needed.
Using smart pointers means we don’t have to deallocate the memory used for the arrays. For smart pointers we can use unique_ptr or shared_ptr. The former makes more sense here, since two stack objects should never share the same element array! However, during resizing, there will be a time when we have to reassign the elements field, so we have to do a std::move.
And of course, we have two additional enhancements over C: (1) classes for information hiding, and (2) exceptions for failing fast!
Security features:
unique_ptr rather than shared_ptr.All the functions here are inline, defined in the class, so we only need a .h file:
// A class for an expandable stack of strings. There is already a stack class
// in the Standard C++ Library; this class is just an illustration of how
// to build such a class from scratch as part of a unit on secure software
// development. It uses smart pointers.
#include <stdexcept>
#include <string>
#include <memory>
using namespace std;
// A stack object wraps a low-level array indexed from 0 to capacity-1 where
// the bottommost element (if it exists) will be in slot 0. The member top is
// the index of the slot above the top element, i.e. the next available slot
// that an element can go into. Therefore if top==0 the stack is empty and
// if top==capacity it needs to be expanded before pushing another element.
// However for security there is still a super maximum capacity that cannot
// be exceeded.
#define MAX_CAPACITY 1048576
#define MAX_ELEMENT_BYTE_SIZE 256
#define INITIAL_CAPACITY 16
class Stack {
// Allocate the data array with a smart pointer, so no destructor needed, woohoo!
unique_ptr<string[]> elements;
int capacity;
int top;
// Prohibit copying and assignment
Stack(Stack&) = delete;
Stack& operator=(Stack&) = delete;
public:
Stack():
top(0),
elements(make_unique<string[]>(INITIAL_CAPACITY)),
capacity(INITIAL_CAPACITY) {
}
int size() {return top;}
bool is_empty() {return top == 0;}
bool is_full() {return top == MAX_CAPACITY;}
void push(string item) {
if (top == MAX_CAPACITY) {
throw overflow_error("Stack has reached maximum capacity");
}
if (item.size() > MAX_ELEMENT_BYTE_SIZE) {
throw range_error("Item is too large");
}
if (top == capacity) {
// No more room, expand if we can
reallocate(capacity * 2);
}
// Strings have value semantics in C++, no need for copy code.
elements[top++] = item;
}
string pop() {
if (is_empty()) {
throw underflow_error("cannot pop from empty stack");
}
if (top < capacity / 4) {
// Too much empty space, contract if we can
reallocate(capacity / 2);
}
string poppedValue = elements[--top];
// For security, blank out the memory holding the popped value so
// and old string doesn't hang around in memory.
elements[top] = "";
// Strings have value semantics in C++, no need for copy code.
return poppedValue;
}
void reallocate(int newCapacity) {
// Prevent capacity from going below initial or above maximum.
newCapacity = max(capacity, INITIAL_CAPACITY);
newCapacity = min(capacity, MAX_CAPACITY);
// Allocate a new array with the new capacity.
unique_ptr<string[]> new_elements = make_unique<string[]>(capacity);
// Copy the elements in the old array to the new array.
std::copy(elements.get(), elements.get() + top, new_elements.get());
// The stack needs to point to the new array. The old array will be
// automatically deleted when reassigned. But we can't just do
// elements = new_elements; because elements is a unique_ptr, so we have to
// use the move() function to transfer ownership of the new array
// to the stack.
elements = std::move(new_elements);
}
};
Here are some tests. No fancy framework, just asserts. On a Unix-like shell run:
g++ -std=c++17 testexpandablestack.cpp && ./a.out
#include <iostream>
#include <cassert>
#include <cmath>
#include <stdexcept>
using namespace std;
#include "SimpleExpandableStack.h"
int main() {
bool error_thrown = false;
Stack s;
assert(s.is_empty() && !s.is_full() && s.size() == 0);
// Individual elements are bounds checked
error_thrown = false;
try {
s.push(string(257, '$'));
} catch (range_error e) {
error_thrown = true;
}
assert(error_thrown);
// Push a lot and pop until empty
for (int i = 1; i <= 50000; i++) {
s.push(to_string(i));
assert(!s.is_empty() && !s.is_full() && s.size() == i);
}
for (int i = 50000; i >= 2; i--) {
string result = s.pop();
assert(result == to_string(i));
assert(!s.is_empty() && !s.is_full() && s.size() == i - 1);
}
string result = s.pop();
assert(result == "1");
assert(s.is_empty() && s.size() == 0);
// Pop from empty stack
error_thrown = false;
try {
s.pop();
} catch (underflow_error e) {
error_thrown = true;
}
assert(error_thrown);
cout << "All tests have passed\n";
return 0;
}
Security features:
import java.nio.charset.StandardCharsets;
// An expandable stack of strings. Both the number of elements in the
// stack and the byte length of each stack element are bounded. The
// class is used to illustrate as many security concepts as possible.
// Strings are immutable in Java so there is no need to make copies when
// pushing or popping.
class SecureExpandableStack {
private static final int MAX_ELEMENT_BYTE_SIZE = 256;
private static final int INITIAL_CAPACITY = 16;
private static final int MAX_CAPACITY = 1048576;
// Classical array-based implementation: top refers to next index to fill
private int top = 0;
private String[] elements = new String[INITIAL_CAPACITY];
// The field `top` is the index of the next array slot to add to
// (one beyond the actual top, i.e., last element added). Hence
// 'top' is also functions as the size (current number of elements).
public int size() {
return top;
}
public boolean full() {
return top == MAX_CAPACITY;
}
public boolean empty() {
return top == 0;
}
public void push(String item) {
if (item.getBytes(StandardCharsets.UTF_8).length > MAX_ELEMENT_BYTE_SIZE) {
throw new IllegalArgumentException("Item is too large");
}
if (top == MAX_CAPACITY) {
throw new IllegalStateException("Cannot push since stack is at max capacity");
}
if (top == elements.length) {
// No more room, expand if we can
reallocate(elements.length * 2);
}
elements[top++] = item;
}
public String pop() {
if (empty()) {
throw new IllegalStateException("Cannot pop from empty stack");
}
if (top <= elements.length / 4) {
// Too much empty space, contract if we can
reallocate(elements.length / 2);
}
var poppedValue = elements[--top];
// For security, blank out the memory holding the popped value
elements[top] = null;
return poppedValue;
}
private void reallocate(int newCapacity) {
// Don't let the capacity exceed the maximum capacity nor go below the
// initial capacity
newCapacity = Math.max(Math.min(newCapacity, MAX_CAPACITY), INITIAL_CAPACITY);
if (newCapacity == elements.length) {
// Don't waste time reallocating to the same size
return;
}
var newData = new String[newCapacity];
System.arraycopy(elements, 0, newData, 0, top);
elements = newData;
}
// A package-private method for testing only. Returns the current
// stack capacity, which we know is the length of the underlying
// representation (the array).
int capacity() {
return elements.length;
}
}
Here are tests done with the most popular framework for Java, namely JUnit. I put the JUnit standalone console launcher into my home folder so I could run the tests with:
javac -cp ~/junit.jar:. SecureExpandableStackTest.java && java -jar ~/junit.jar -cp . -c SecureExpandableStackTest
But running under VSCode or any IDE is just fine too.
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.BeforeEach;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.NoSuchElementException;
public class SecureExpandableStackTest {
SecureExpandableStack s;
@BeforeEach
public void makeSecureExpandableStack() {
s = new SecureExpandableStack();
}
@Test
public void testNewStackIsEmpty() {
assertTrue(s.empty());
assertEquals(0, s.size());
}
@Test
public void testPushesToEmptyStack() {
int numberOfPushes = 8;
for (var i = 0; i < numberOfPushes; i++) {
s.push("zzz");
}
assertFalse(s.empty());
assertEquals(numberOfPushes, s.size());
}
@Test
public void testPushThenPop() {
var message = "hello";
s.push(message);
assertEquals(message, s.pop());
}
@Test
public void testPoppingDownToEmpty() {
int numberOfPushes = 8;
for (var i = 0; i < numberOfPushes; i++) {
s.push("zzz");
}
for (var i = 0; i < numberOfPushes; i++) {
s.pop();
}
assertTrue(s.empty());
assertEquals(0, s.size());
}
@Test
public void testPopOnEmptyStackThrows() {
assertTrue(s.empty());
assertThrows(IllegalStateException.class, () -> s.pop());
}
@Test
public void inidividualElementsAreBoundsChecked() {
var largeString = "a".repeat(257);
assertThrows(IllegalArgumentException.class, () -> s.push(largeString));
}
@Test
public void testPushToFullStackGrowsTheStack() {
int initialCapacity = s.capacity();
for (var i = 0; i < initialCapacity; i++) {
assertEquals(initialCapacity, s.capacity());
s.push("abc");
}
assertEquals(s.size(), s.capacity());
s.push("First value");
assertEquals(s.size(), initialCapacity + 1);
assertEquals(initialCapacity * 2, s.capacity());
while (s.size() < initialCapacity * 2) {
assertEquals(initialCapacity * 2, s.capacity());
s.push("abc");
}
assertEquals(initialCapacity * 2, s.capacity());
s.push("abc");
assertEquals(initialCapacity * 4, s.capacity());
}
@Test
public void testStackGetsSmallerWhenTooSparse() {
int initialCapacity = s.capacity();
for (var i = 0; i < initialCapacity * 4; i++) {
s.push("abc");
}
s.push("abc");
assertEquals(initialCapacity * 4 + 1, s.size());
assertEquals(initialCapacity * 8, s.capacity());
s.pop();
assertEquals(initialCapacity * 4, s.size());
assertEquals(initialCapacity * 8, s.capacity());
for (var i = 0; i < initialCapacity * 2; i++) {
s.pop();
}
assertEquals(initialCapacity * 2, s.size());
assertEquals(initialCapacity * 8, s.capacity());
s.pop();
assertEquals(initialCapacity * 2 - 1, s.size());
assertEquals(initialCapacity * 4, s.capacity());
}
@Test
public void testStackDoesNotShrinkWhenCapacityAtMinium() {
int initialCapacity = s.capacity();
for (var i = 0; i < initialCapacity; i++) {
s.push("abc");
assertEquals(initialCapacity, s.capacity());
}
for (var i = 0; i < initialCapacity; i++) {
s.pop();
assertEquals(initialCapacity, s.capacity());
}
}
}