Are unconstrained arrays in Ada safe to use?

user_15093079 0
Viewed 351

I was reading up on array types in Ada and found it interesting that, unlike C++, the language allows their size to be unknown at compile time. I was not sure how they are implemented though so I wrote a small test:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Command_Line; use Ada.Command_Line;

procedure Main is
   type Data is array (1 .. 131_072) of Integer;
   type Vector is array (Positive range <>) of Data;
   Sequence : Vector (1 .. Argument_Count);
begin
   for I in Sequence'Range loop
      Sequence (I) := (others => I);
      Put (Integer'Image (Sequence (I)(1)));
   end loop;
end Main;

And then tried to replicate this code in C using variable length arrays:

#include <stdio.h>

struct data {
    int x[131072];
};

int main(int argc, char** argv) {
    (void)argv;
    struct data sequence[argc - 1];
    for (int i = 0; i < argc - 1; i++) {
        for (int j = 0; j < 131072; j++)
            sequence[i].x[j] = i;
        printf("%i ", sequence[i].x[1]);
    }
}

I compiled both with gnatmake -gnato -fstack-check -gnat2012 -gnata -O3 main.adb -o main and gcc -O3 -Wall -Werror -Wextra -pedantic cmain.c -o cmain. After running the programs, both were failing when given 16 or more arguments - the difference was that cmain simply segfaulted while main ended up raising "STORAGE_ERROR : stack overflow or erroneous memory access".

Since both VLAs and unconstrained arrays seem to be (at least on surface) implemented in a similar manner and the former is widely considered to be not safe to use in nearly all circumstances, is it safe to use the latter?

variable-length-array ada c
2 Answers

Unconstrained array types in Ada are not by themselves unsafe; what is unsafe, or at least may lead to an exception, is using an unchecked input value (such as Argument_Count) to create an array object of that size. If you do that, and don't have an exception handler, an attacker can make your program abort with an unhandled exception, as in your example.

Note that unconstrained array types are used in Ada in two ways:

  1. To create array objects of a dynamically determined size, as in your example.
  2. To pass arrays of various sizes as parameters to subprograms, even if the actual array objects have statically defined sizes.

The second use (parameters) is completely safe, of course, and the actual bounds of the parameter can be accessed as usual by A'First, A'Last, A'Range, A'Length.

user_150040770

Unconstrained arrays are not intrinsically unsafe. See the example below implementing parallel addition of array elements.

package Parallel_Addition is
   type Data_Array is array(Integer range <>) of Integer;
   type Data_Access is access all Data_Array;
   function Sum(Item : in not null Data_Access) return Integer;
end Parallel_Addition;

Note that the package specification above declares an unconstrained array type. It also declares an access type to the unconstrained array type so that very large arrays can be dynamically allocated, avoiding stack exhaustion problems.

package body Parallel_Addition is

   ---------
   -- Sum --
   ---------

   function Sum (Item : in not null Data_Access) return Integer is
      task type Adder is
         entry Set (Min : Integer; Max : Integer);
         entry Report (Value : out Integer);
      end Adder;

      task body Adder is
         Total : Integer := 0;
         First : Integer;
         Last  : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;
         for I in First .. Last loop
            Total := Total + Item (I);
         end loop;
         accept Report (Value : out Integer) do
            Value := Total;
         end Report;
      end Adder;
      A1  : Adder;
      A2  : Adder;
      R1  : Integer;
      R2  : Integer;
      Mid : constant Integer := (Item'Length / 2) + Item'First;
   begin
      A1.Set (Min => Item'First, Max => Mid);
      A2.Set (Min => Mid + 1, Max => Item'Last);
      A1.Report (R1);
      A2.Report (R2);
      return R1 + R2;
   end Sum;

end Parallel_Addition;

No problems using the unconstrained array instance in the function Sum. Let's try test this package using a very large dynamically allocated array.

with Parallel_Addition; use Parallel_Addition;
with Ada.Text_IO;       use Ada.Text_IO;
with Ada.Calendar;      use Ada.Calendar;

procedure Parallel_Addition_Test is
   The_Data : Data_Access := new Data_Array (1 .. Integer'Last);
   Start    : Time;
   Stop     : Time;
   The_Sum  : Integer;

begin
   The_Data.all := (others => 1);
   Start        := Clock;
   The_Sum      := Sum (The_Data);
   Stop         := Clock;
   Put_Line ("The sum is: " & Integer'Image (The_Sum));
   Put_Line
     ("Addition elapsed time is " &
      Duration'Image (Stop - Start) &
        " seconds.");
   Put_Line
     ("Time per addition operation is " &
        Float'Image(Float(Stop - Start) / Float(The_Data'Length)) &
        " seconds.");
end Parallel_Addition_Test;

When executed on my Windows 10 PC I get the following output:

The sum is:  2147483647
Addition elapsed time is  5.141288000 seconds.
Time per addition operation is  2.39410E-09 seconds.
user_68544070
Related