Лабораторная работа Задание 1: Надёжность программного обеспечения бесплатно 226141

Василенко Анатолий

421 группа

//====================================== ======================================== ======================================== ===============================

1 часть задания:

/////////////////////////

количество переменных - h, f_a, f_b, f_x, f_y, g_a, g_b, g_x, g_y - 9 штук

переменные размерности int, что значит, что каждая переменная может принимать 2^32 различных значений

операторы пронумерованны ниже:

/////////////////////////

int h;

void f (int a, int b)

{

0: int x, y;

1: x = 9;

2: y = 3;

3: h = 3;

4: h = a + y;

5: if (y > 6)

{

6: if (x > 9)

{

7: y = 4;

}

8: if (h < a + x)

{

9: h = y;

}

10: x = 5;

}

11: } // заключительный оператор

// Всего 12 операторов

void g (int a, int b)

{

0: int x, y;

1: x = 2;

2: y = 7;

3: h = 5;

4: x = 4;

5: h = b;

6: if (h < y)

{

7: y = 0;

}

else

{

8: x = 3;

}

9: while (x > 4)

{

10: if (h > 0)

11: break;

12: x = 1;

13: if (x > 5)

{

14: y = 6;

}

15: h = y;

}

16:} // Заключительное состояние

// Всего 17 операторов

/////////////////////////

Это означает, что количество потенциальных состояний программы = 12*17*(2^(32*9)) = 204*2^(288)

(Без учёта недостижимости)

Ответ: 12*17*(2^(32*9)) = 204 * 2^288

//====================================== ======================================== ======================================== ===============================

2 часть задания:

Проверим всё на достижимость:

/////////////////////////

// исходя из функции g - h на входе может быть равна {#} или {5, g_b, g_y}, причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции g, то придётся всё время считать, что h может быть изменено на {5, g_b, g_y}

int h;

void f (int a, int b)

{

0: int x, y; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1)

1: x = 9; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {#}; f_y = {#}

2: y = 3; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {#}

3: h = 3; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

4: h = a + y; // h = {3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

5: if (y > 6) // h = {f_a+f_y = f_a+3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

{ // недостижимо, т.к. в условии стоит y > 6 , в то время, как f_y = {3}

6: if (x > 9) // недостижимо

{ // недостижимо

7: y = 4; // недостижимо

} // недостижимо

8: if (h < a + x) // недостижимо

{ // недостижимо

9: h = y; // недостижимо

} // недостижимо

10: x = 5; // недостижимо

} // недостижимо

11: } // заключительный оператор

// h = {f_a+3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

// Исходя из уже проанализированной функции f (т.е. за вычетом недостижимых участков) - h на входе может быть равна {#} или {f_a+3, 3, f_y} (f_y - тоже, потому что недостижимость будет учтена позже на следующем раунде), причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции f, то придётся всё время считать, что h может быть изменено на {f_a+3, 3, f_y}

void g (int a, int b)

{

0: int x, y; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1)

1: x = 2; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {#}; g_y = {#}

2: y = 7; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {#}

3: h = 5; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7}

4: x = 4; // h = {5, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7}

5: h = b; // h = {5, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}

6: if (h < y) // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}

{

7: y = 0; // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h < g_y)

}

else

{

8: x = 3; // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h >= g_y)

}

9: while (x > 4) // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7))

{ // недостижимо, потому что g_x принимает значение 3 или 4, а в условии цикла g_x > 4

10: if (h > 0) // недостижимо

11: break; // недостижимо

12: x = 1; // недостижимо

13: if (x > 5) // недостижимо

{ // недостижимо

14: y = 6; // недостижимо

} // недостижимо

15: h = y; // недостижимо

} // недостижимо

16:} // Заключительное состояние

// h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7))

/////////////////////////

Теперь, после того, как некоторые части функций были объявлены, как недостижимые, это могло повлиять на комбинации условий, что может привести к дальнейшему уменьшению количества состояний, поэтому пересмотрим функции ещё раз, но уже без недостижимых состояний (и сменим нумерацию на новую)

// исходя из функции g - h на входе может быть равна {#} или {5, g_b}, причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции g, то придётся всё время считать, что h может быть изменено на {5, g_b}

int h;

Продолжение текста

Дано:

Дан текст программы на языке С с функциями f и g.

Предполагается, что функции f и g выполняются параллельно, в двух разных потоках управления (процессах) P_f и P_g соответственно. Будем считать состоянием модели программы совокупность значений счётчиков команд c_f и c_g процессов P_f и P_g, значения глобальных и локальных переменных заданной программы.

Неинициализированные переменные принимают специальное значение, обозначаемое символом #, лежащее вне диапазона MININT..MAXINT.

Требуется:

1. (1 балл) Оценить размер множества потенциальных состояний программы. Ответ обосновать.

2. (2 балла) Оценить размер множества достижимых состояний программы. Ответ обосновать. В обосновании описать множество достижимых состояний с помощью линейных равенств и неравенств на языке C.

Например, (c_f == 3 && a < 5) || (c_g == 4 && b > d).

3. (7 баллов) Написать программу на языке С, которая вычисляет и записывает в текстовой файл states.txt множество достижимых состояний заданной программы для заданных значений параметров функций, а также выводит в стандартный поток вывода количество достижимых состояний.

На выполнение задания отводится две недели.

Требования к файлам решения:

Решение задачи должно включать в себя 3 файла, НЕ ЗАПАКОВАННЫЕ В АРХИВ:

1.Исходная формулировка задачи с именем task.txt

2.Описание решения пп. 1-2 в текстовом файле с именем solution.txt. Текстовый файл должен быть в одной из кодировок: utf8, cp1251 (Windows), koi8-r. Файлы других форматов (doc, pdf, etc) не принимаются.

3.Файл group_surname.c с программой подсчёта состояний (group - номер вашей группы, surname - ваша фамилия латиницей).

Требования к программе:

1.Программа должны вычислять множество достижимых состояний программы, присланной вам на почту, для заданных значений параметров функций f и g.

2.Программа должна уметь выводить множество состояний в текстовой файл в формате: значение счётчика f, значение счётчика g, значение h, значение f.x, значение f.y, значение g.x, значение g.y, (через запятую) по одному состоянию в строке. Значения счётчиков нумеруются с 0. Первая строка файла должна содержать описание формата вывода, а именно: c_f, c_g, h, f.x, f.y, g.x, g.y. Обратите внимание, что смена состояния программы происходит после выполнения соответствующего оператора программы (например, присваивания).

3.Программа должны выполняться в консоли. Обязательными входными параметрами являются значения параметров функций a и b в следующем порядке:

имя_программы <f_a> <f_b> <g_a> <g_b>

Также должны поддерживаться параметры:

-file имя_файла - запись состояний в указанный файл,

-count - вывод общего количества состояний программы в стандартный поток вывода.

При запуске без параметров (либо с недостаточным количеством параметров) программа должна выводить информацию о программе, авторе, годе написания и параметрах запуска.

4.Исходный код программы должен содержать информацию об авторе и годе написания программы.

5.Программа должна быть написана на языке ANSI C либо ANSI/ISO C++.

6.Программа должна успешно компилироваться компилятором gcc со следующими параметрами: gcc -O2 -Wall -Werror.

7.Допускается использование только библиотек stdlib и STL.

8.Текст программы должен быть снабжён исчерпывающими комментариями. Как минимум, должны быть прокомментированы все объявления функций, операторы ветвления и линейные участки программы.

9.Программа должна быть написана самостоятельно. При заимствовании фрагментов кода из open-source проектов должен быть указан автор кода. Заимствовать код из решений предыдущего года не допускается. Если будет обнаружено, что несколько присланных решений написаны одним человеком, оценка будет снижена для всех похожих работ. Для анализа схожести кода будут использованы соответствующие инструментальные средства.

Последний срок сдачи задания - 07 октября. Методические указания по решению задания можно найти по адресу: http://lvk.cs.msu.su/~dimawolf/SoftwareR eliability/Task01.pdf

Программа для анализа:

int h;

void

f (int a, int b)

{

int x, y;

x = 9;

y = 3;

h = 3;

h = a + y;

if (y > 6)

{

if (x > 9)

{

y = 4;

}

if (h < a + x)

{

h = y;

}

x = 5;

}

void

g (int a, int b)

{

int x, y;

x = 2;

y = 7;

h = 5;

x = 4;

h = b;

if (h < y)

{

y = 0;

}

else

{

x = 3;

}

while (x > 4)

{

if (h > 0)

break;

x = 1;

if (x > 5)

{

y = 6;

}

h = y;

}

Василенко Анатолий

421 группа

//====================================== ======================================== ======================================== ===============================

1 часть задания:

/////////////////////////

количество переменных - h, f_a, f_b, f_x, f_y, g_a, g_b, g_x, g_y - 9 штук

переменные размерности int, что значит, что каждая переменная может принимать 2^32 различных значений

операторы пронумерованны ниже:

/////////////////////////

int h;

void f (int a, int b)

{

0: int x, y;

1: x = 9;

2: y = 3;

3: h = 3;

4: h = a + y;

5: if (y > 6)

{

6: if (x > 9)

{

7: y = 4;

}

8: if (h < a + x)

{

9: h = y;

}

10: x = 5;

}

11: } // заключительный оператор

// Всего 12 операторов

void g (int a, int b)

{

0: int x, y;

1: x = 2;

2: y = 7;

3: h = 5;

4: x = 4;

5: h = b;

6: if (h < y)

{

7: y = 0;

}

else

{

8: x = 3;

}

9: while (x > 4)

{

10: if (h > 0)

11: break;

12: x = 1;

13: if (x > 5)

{

14: y = 6;

}

15: h = y;

}

16:} // Заключительное состояние

// Всего 17 операторов

/////////////////////////

Это означает, что количество потенциальных состояний программы = 12*17*(2^(32*9)) = 204*2^(288)

(Без учёта недостижимости)

Ответ: 12*17*(2^(32*9)) = 204 * 2^288

//====================================== ======================================== ======================================== ===============================

2 часть задания:

Проверим всё на достижимость:

/////////////////////////

// исходя из функции g - h на входе может быть равна {#} или {5, g_b, g_y}, причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции g, то придётся всё время считать, что h может быть изменено на {5, g_b, g_y}

int h;

void f (int a, int b)

{

0: int x, y; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1)

1: x = 9; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {#}; f_y = {#}

2: y = 3; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {#}

3: h = 3; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

4: h = a + y; // h = {3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

5: if (y > 6) // h = {f_a+f_y = f_a+3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

{ // недостижимо, т.к. в условии стоит y > 6 , в то время, как f_y = {3}

6: if (x > 9) // недостижимо

{ // недостижимо

7: y = 4; // недостижимо

} // недостижимо

8: if (h < a + x) // недостижимо

{ // недостижимо

9: h = y; // недостижимо

} // недостижимо

10: x = 5; // недостижимо

} // недостижимо

11: } // заключительный оператор

// h = {f_a+3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}

// Исходя из уже проанализированной функции f (т.е. за вычетом недостижимых участков) - h на входе может быть равна {#} или {f_a+3, 3, f_y} (f_y - тоже, потому что недостижимость будет учтена позже на следующем раунде), причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции f, то придётся всё время считать, что h может быть изменено на {f_a+3, 3, f_y}

void g (int a, int b)

{

0: int x, y; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1)

1: x = 2; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {#}; g_y = {#}

2: y = 7; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {#}

3: h = 5; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7}

4: x = 4; // h = {5, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7}

5: h = b; // h = {5, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}

6: if (h < y) // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}

{

7: y = 0; // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h < g_y)

}

else

{

8: x = 3; // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h >= g_y)

}

9: while (x > 4) // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7))

{ // недостижимо, потому что g_x принимает значение 3 или 4, а в условии цикла g_x > 4

10: if (h > 0) // недостижимо

11: break; // недостижимо

12: x = 1; // недостижимо

13: if (x > 5) // недостижимо

{ // недостижимо

14: y = 6; // недостижимо

} // недостижимо

15: h = y; // недостижимо

} // недостижимо

16:} // Заключительное состояние

// h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7))

/////////////////////////

Теперь, после того, как некоторые части функций были объявлены, как недостижимые, это могло повлиять на комбинации условий, что может привести к дальнейшему уменьшению количества состояний, поэтому пересмотрим функции ещё раз, но уже без недостижимых состояний (и сменим нумерацию на новую)

Продолжение текста

Дано:

Дан текст программы на языке С с функциями f и g.

Предполагается, что функции f и g выполняются параллельно, в двух разных потоках управления (процессах) P_f и P_g соответственно. Будем считать состоянием модели программы совокупность значений счётчиков команд c_f и c_g процессов P_f и P_g, значения глобальных и локальных переменных заданной программы.

Неинициализированные переменные принимают специальное значение, обозначаемое символом #, лежащее вне диапазона MININT..MAXINT.

Требуется:

1. (1 балл) Оценить размер множества потенциальных состояний программы. Ответ обосновать.

2. (2 балла) Оценить размер множества достижимых состояний программы. Ответ обосновать. В обосновании описать множество достижимых состояний с помощью линейных равенств и неравенств на языке C.

Например, (c_f == 3 && a < 5) || (c_g == 4 && b > d).

3. (7 баллов) Написать программу на языке С, которая вычисляет и записывает в текстовой файл states.txt множество достижимых состояний заданной программы для заданных значений параметров функций, а также выводит в стандартный поток вывода количество достижимых состояний.

На выполнение задания отводится две недели.

Требования к файлам решения:

Решение задачи должно включать в себя 3 файла, НЕ ЗАПАКОВАННЫЕ В АРХИВ:

1.Исходная формулировка задачи с именем task.txt

2.Описание решения пп. 1-2 в текстовом файле с именем solution.txt. Текстовый файл должен быть в одной из кодировок: utf8, cp1251 (Windows), koi8-r. Файлы других форматов (doc, pdf, etc) не принимаются.

3.Файл group_surname.c с программой подсчёта состояний (group - номер вашей группы, surname - ваша фамилия латиницей).

Требования к программе:

1.Программа должны вычислять множество достижимых состояний программы, присланной вам на почту, для заданных значений параметров функций f и g.

2.Программа должна уметь выводить множество состояний в текстовой файл в формате: значение счётчика f, значение счётчика g, значение h, значение f.x, значение f.y, значение g.x, значение g.y, (через запятую) по одному состоянию в строке. Значения счётчиков нумеруются с 0. Первая строка файла должна содержать описание формата вывода, а именно: c_f, c_g, h, f.x, f.y, g.x, g.y. Обратите внимание, что смена состояния программы происходит после выполнения соответствующего оператора программы (например, присваивания).

3.Программа должны выполняться в консоли. Обязательными входными параметрами являются значения параметров функций a и b в следующем порядке:

имя_программы <f_a> <f_b> <g_a> <g_b>

Также должны поддерживаться параметры:

-file имя_файла - запись состояний в указанный файл,

-count - вывод общего количества состояний программы в стандартный поток вывода.

При запуске без параметров (либо с недостаточным количеством параметров) программа должна выводить информацию о программе, авторе, годе написания и параметрах запуска.

4.Исходный код программы должен содержать информацию об авторе и годе написания программы.

5.Программа должна быть написана на языке ANSI C либо ANSI/ISO C++.

6.Программа должна успешно компилироваться компилятором gcc со следующими параметрами: gcc -O2 -Wall -Werror.

7.Допускается использование только библиотек stdlib и STL.

8.Текст программы должен быть снабжён исчерпывающими комментариями. Как минимум, должны быть прокомментированы все объявления функций, операторы ветвления и линейные участки программы.

9.Программа должна быть написана самостоятельно. При заимствовании фрагментов кода из open-source проектов должен быть указан автор кода. Заимствовать код из решений предыдущего года не допускается. Если будет обнаружено, что несколько присланных решений написаны одним человеком, оценка будет снижена для всех похожих работ. Для анализа схожести кода будут использованы соответствующие инструментальные средства.

Последний срок сдачи задания - 07 октября. Методические указания по решению задания можно найти по адресу: http://lvk.cs.msu.su/~dimawolf/SoftwareR eliability/Task01.pdf

Программа для анализа:

int h;

void

f (int a, int b)

{

int x, y;

x = 9;

y = 3;

h = 3;

h = a + y;

if (y > 6)

{

if (x > 9)

{

y = 4;

}

if (h < a + x)

{

h = y;

}

x = 5;

}

void

g (int a, int b)

{

int x, y;

x = 2;

y = 7;

h = 5;

x = 4;

h = b;

if (h < y)

{

y = 0;

}

else

{

x = 3;

}

while (x > 4)

{

if (h > 0)

break;

x = 1;

if (x > 5)

{

y = 6;

}

h = y;

}

Лабораторная работа: Задание 1

Описание

Характеристики лабораторной работы

Список файлов

Комментарии