sleirsgoevy Aug 18 2019 at 16:05

Анализ языка VKScript: JavaScript, ты ли это?

9 min

26K

JavaScript*Reverse engineering*VK API*

From sandbox

TL;DR

VKScript — это не JavaScript. Семантика этого языка кардинально отличается от семантики JavaScript. См. заключение.

Что такое VKScript?

VKScript — скриптовый язык программирования, похожий на JavaScript, который используется в методе execute API ВКонтакте, который дает клиентам возможность загружать ровно ту информацию, которая им нужна. По сути, VKScript — это аналог GraphQL, используемого в Facebook для тех же целей.

Сравнение GraphQL и VKScript:

	GraphQL	VKScript
Реализации	Множество open-source реализаций на разных языках программирования	Единственная реализация в рамках API ВКонтакте
Основан на	Абсолютно новый язык	JavaScript
Возможности	Запрос данных, ограниченная фильтрация; аргументы запроса не могут использовать результаты предыдущих запросов	Любая пост-обработка данных на усмотрение клиента; запросы к API представлены в виде методов и могут использовать любые данные из предыдущих запросов

Описание VKScript со страницы метода в документации VK API (единственная официальная документация по языку):

code код алгоритма в VKScript — формате, похожем на JavaSсript или ActionScript (предполагается совместимость с ECMAScript). Алгоритм должен завершаться командой return %выражение%. Операторы должны быть разделены точкой с запятой.
строка

Поддерживаются:

арифметические операции

логические операции

создание массивов и списков ([X,Y])

parseInt и parseDouble

конкатенация (+)

конструкция if

фильтр массива по параметру (@.)

вызовы методов API, параметр length

циклы, используя оператор while

методы Javascript: slice, push, pop, shift, unshift, splice, substr, split

оператор delete

присваивания элементам маcсива, например: row.user.action = «test»;

поиск в массиве или строке — indexOf, например: «123».indexOf(2) = 1, [1, 2, 3].indexOf(3) = 2. Возвращает -1, если элемент не найден.

В данный момент не поддерживается создание функций.

code	код алгоритма в VKScript — формате, похожем на JavaSсript или ActionScript (предполагается совместимость с ECMAScript). Алгоритм должен завершаться командой return %выражение%. Операторы должны быть разделены точкой с запятой. строка

В приведенной документации указано, что «планируется совместимость с ECMAScript». Но так ли это? Попробуем разобраться, как этот язык работает изнутри.

Содержание

Виртуальная машина VKScript
Семантика объектов VKScript
Заключение

Виртуальная машина VKScript

Как вообще можно анализировать программу при отсутствии локальной копии? Правильно — отправлять запросы к публичному endpoint'у и анализировать ответы. Попробуем, например, выполнить такой код:

while(1);

Мы получаем ошибку Runtime error occurred during code invocation: Too many operations. Это говорит о том, что в реализации языка присутствует лимит на количество произведенных действий. Попробуем установить точное значение лимита:

var i = 0;
while(i < 1000)
    i = i + 1;

Runtime error occurred during code invocation: Too many operations.

var i = 0;
while(i < 999)
    i = i + 1;

{"response": null} — код успешно выполнился.

Таким образом, лимит на количество операций — порядка 1000 «холостых» циклов. Но, в то же время, понятно, что такой цикл, скорее всего, не является «унитарной» операцией. Попробуем найти операцию, которая не разделяется компилятором на несколько более мелких.

Самым очевидным кандидатом на роль такой операции является так называемый empty statement (;). Однако после добавления к коду с i < 999 50 символов ;, превышения лимита не происходит. Это означает, что либо empty statement выбрасывается компилятором и не тратит операции, либо одна итерация цикла занимает больше 50 операций (что, скорее всего, не так).

Следующее, что приходит в голову после ; — вычисление какого-нибудь простого выражения (например, так: 1;). Попробуем добавить несколько таких выражений в наш код:

var i = 0;
while(i < 999)
    i = i + 1;
1; // так еще работает
1; // при добавлении этой строки получаем ошибку "Too many operations"

Таким образом, 2 операции 1; тратят больше операций, чем 50 операция ;. Это подтверждает гипотезу о том, что empty statement не тратит инструкций.

Попробуем уменьшать количество итераций цикла и добавлять дополнительные 1;. Несложно заметить, что на каждую итерацию приходится 5 дополнительных 1;, следовательно, одна итерация цикла тратит в 5 раз больше операций, чем одна операция 1;.

Но нет ли еще более простой операции? Например, добавление унарного оператора ~ не требует вычисления дополнительных выражений, а сама операция выполняется на процессоре. Логично предположить, что добавление в выражение этой операции увеличивает общее количество операций на 1.

Добавим в наш код этот оператор:

var i = 0;
while(i < 999)
    i = i + 1;
~1;

И да, один такой оператор мы добавить можем, а еще одно выражение 1; — уже нет. Следовательно, 1; действительно не является унитарным оператором.

Аналогично оператору 1;, будем уменьшать количество итераций цикла и добавлять операторы ~. Одна итерация оказалась эквивалентна 10 унитарным операциям ~, следовательно, выражение 1; тратит 2 операции.

Заметим, что лимит составляет примерно 1000 итераций, то есть примерно 10000 единичных операций. Будем считать, что лимит составляет точно 10000 операций.

Измерение количества операций в коде

Заметим, что теперь мы можем измерять количество операций в любом коде. Для этого нужно добавить этот код после цикла и добавлять/удалять итерации, операторы ~ или всю последнюю строку целиком, пока ошибка Too many operations не исчезнет.

Некоторые результаты измерений:

Код	Количество операций
`1;`	2
`~1;`	3
`1+1;`	4
`1+1+1;`	6
`(true?1:1);`	5
`(false?1:1);`	4
`if(0)1;`	2
`if(1)1;`	4
`if(0)1;else 1;`	4
`if(1)1;else 1;`	5
`while(0);`	2
`i=1;`	3
`i=i+1;`	5
`var j = 1;`	1
`var j = 0;while(j < 1)j=j+1;`	15

Определение типа виртуальной машины

Для начала нужно понять, по какому принципу работает интерпретатор VKScript. Есть два более-менее правдоподобных варианта:

Интерпретатор рекурсивно обходит синтаксическое дерево и выполняет операцию в каждом узле.
Компилятор переводит синтаксическое дерево в последовательность инструкций, которые выполняет интерпретатор.

Несложно понять, что в VKScript используется второй вариант. Рассмотрим выражения (true?1:1); (5 операций) и (false?1:1); (4 операции). В случае с последовательным выполнением инструкций дополнительная операция объясняется переходом, который «обходит» неверный вариант, а в случае с рекурсивным обходом AST оба варианта для интерпретатора равноценны. Аналогичный эффект наблюдается в if/else с разным условием.

Также стоит обратить внимание на пару i = 1; (3 операции) и var j = 1; (1 операция). Создание новой переменной обходится всего в 1 операцию, а присвоение в существующую — в 3? То, что создание переменной обходится в 1 операцию (и то, это, скорее всего, операция загрузки константы), говорит о двух вещах:

При создании новой переменной не происходит явного выделения памяти под переменную.
При создании новой переменной не происходит загрузки значения в ячейку памяти. Это означает, что место под новую переменную выделяется там, где было вычислено значение выражения, и после этого эта память считается выделенной. Это говорит об использовании стековой машины.

Использованием стека также объясняется то, что выражение var j = 1; выполняется быстрее, чем выражение 1;: последнее выражение тратит дополнительную инструкцию на то, чтобы убрать со стека вычисленное значение.

Определение точного значения лимита

Заметим, что цикл var j=0;while(j < 1)j=j+1; (15 операций) — это уменьшенная копия цикла, который использовался для измерений:

Код	Количество операций
`var i = 0; while(i < 1) i = i + 1;`	15
`var i = 0; while(i < 999) i = i + 1;`	15 + 998 * 10 = 9995
`var i = 0; while(i < 999) i = i + 1; ~1;` (лимит)	9998

Стоп, что? Лимит составляет 9998 инструкций? Мы явно что-то упускаем...

Заметим, что код return 1; выполняется, согласно измерениям, за 0 инструкций. Это легко объясняется: компилятор добавляет в конце кода неявный return null;, и при добавлении своего return'а он не выполняется. Считая, что лимит равен 10000, делаем вывод, что операция return null; занимает 2 инструкции (вероятно, это что-то вроде push null; return;).

Вложенные блоки кода

Проведем еще несколько измерений:

Код	Количество операций
`{};`	0
`{var j = 1;};`	2
`{var j = 1, k = 2;};`	3
`{var j = 1; var k = 2;};`	3
`var j = 1; var j = 1;`	4
`{var j = 1;}; var j = 1;`	3

Обратим внимание на следующие факты:

При добавлении переменной в блок тратится одна дополнительная операция.
При «объявлении переменной заново» второе объявление отрабатывает как обычное присваивание.
Но при этом переменная внутри блока снаружи не видна (см. последний пример).

Несложно понять, что лишняя операция тратится на удаление со стека локальных переменных, объявленных в блоке. Соответственно, когда локальных переменных нет, удалять ничего не нужно.

Объекты, методы, вызовы API

Код	Количество операций
`"";`	2
`"abcdef";`	2
`{};`	2
`[];`	2
`[1, 2, 3];`	5
`{a: 1, b: 2, c: 3};`	5
`API.users.isAppUser(1);`	3
`"".substr(0, 0);`	6
`var j={};j.x=1;`	6
`var j={x:1};delete j.x;`	6

Проанализируем полученные результаты. Можно заметить, что создание строки и пустого массива/объекта занимает 2 операции, так же как и загрузка числа. При создании непустого массива или объекта добавляются операции, потраченные на загрузку элементов массива/объекта. Это говорит о том, что непосредственно создание объекта происходит за одну операцию. При этом на загрузку названий свойств время не тратится, следовательно, их загрузка является частью операции создания объекта.

С вызовом метода API все тоже весьма банально — загрузка единицы, собственно вызов метода, pop результата (можно заметить, что название метода обрабатывается как единое целое, а не как взятие свойств). А вот последние три примера выглядят интересно.

"".substr(0, 0); — загрузка строки, загрузка нуля, загрузка нуля, pop результата. На вызов метода почему-то приходится 2 инструкции (почему — см. далее).
var j={};j.x=1; — создание объекта, загрузка объекта, загрузка единицы, pop единицы после присваивания. Опять-таки, на присваивание приходится 2 инструкции.
var j={x:1};delete j.x; — загрузка единицы, создание объекта, загрузка объекта, удаление. На операцию удаления приходится 3 инструкции.

Семантика объектов VKScript

Числа

Вернемся к исходному вопросу: VKScript — это подмножество JavaScript или другой язык? Проведем простой тест:

return 1000000000 + 2000000000;

{"response": -1294967296};

Как мы видим, целочисленное сложение приводит к переполнению, несмотря на то, что в JavaScript нет целых чисел как таковых. Также несложно убедиться, что деление на 0 приводит к ошибке, а не возвращает Infinity.

Объекты

return {};

{"response": []}

Стоп, что? Мы возвращаем объект и получаем массив? Да, так и есть. В языке VKScript массивы и объекты представлены одним типом, в частности, пустой объект и пустой массив это одно и тоже. При этом свойство length у объекта работает и возвращает количество свойств.

Интересно посмотреть, как поведут себя методы списка, если вызвать их на объекте?

return {a:1, b:2, c:3}.pop();

Метод pop возвращает последнее объявленное свойство, что, впрочем, логично. Поменяем порядок свойств:

return {b:1, c:2, a:3}.pop();

Видимо, объекты в VKScript запоминают порядок присвоения свойств. Попробуем использовать числовые свойства:

return {'2':1,'1':2,'0':3}.pop();

Теперь посмотрим, как работает push:

var a = {'2':'a','1':'b','x':'c'};
a.push('d');
return a;

{"1": "b", "2": "a", "3": "d", "x": "c"};

Как видим, метод push сортирует численные ключи и добавляет новое значение после последнего численного ключа. «Дыры» при этом не заполняются.

Теперь попробуем объединить два этих метода:

var a = {'2':'a','1':'b','x':'c'};
a.push(a.pop());
return a;

{"1": "b", "2": "a", "3": "c", "x": "c"};

Как мы видим, элемент не удалился из массива. Однако, если мы разнесем push и pop в разные строки, баг пропадет. We need to go deeper!

Хранение объектов

var x = {};
var y = x;
x.y = 'z';
return y;

{"response": []}

Как выяснилось, объекты в VKScript хранятся по значению, в отличие от JavaScript. Теперь понятно странное поведение строки a.push(a.pop()); — видимо, старое значение массива сохранилось на стеке, откуда потом и было взято.

Однако как тогда данные сохраняются в объект, если метод его изменяет? Видимо, «лишняя» инструкция при вызове метода предназначена именно для записи изменений обратно в объект.

Методы массивов

Метод Действие

Метод	Действие
`push`	отсортировать числовые ключи по значению взять максимальный числовой ключ, прибавить единицу записать аргумент в массив добавить в конец массива нечисловые ключи
`pop`	Убрать из массива последний элемент (не обязательно с числовым ключом) и вернуть.
остальные	отсортировать числовые ключи по значению, убрать «дыры» в массиве выполнить соответствующую операцию JavaScript добавить в конец массива нечисловые ключи При использовании метода slice изменения не сохраняются

push

отсортировать числовые ключи по значению
взять максимальный числовой ключ, прибавить единицу
записать аргумент в массив
добавить в конец массива нечисловые ключи

pop Убрать из массива последний элемент (не обязательно с числовым ключом) и вернуть.

остальные

отсортировать числовые ключи по значению, убрать «дыры» в массиве
выполнить соответствующую операцию JavaScript
добавить в конец массива нечисловые ключи

При использовании метода slice изменения не сохраняются

Заключение

VKScript — это не JavaScript. В отличие от JavaScript, объекты в нем хранятся по значению, а не по ссылке, и обладают совершенно другой семантикой. Однако при использовании VKScript для цели, для которой он предназначен, разница незаметна.

P.S. Семантика операторов

В комментариях упомянули объединение объектов через +. В связи с этим решил добавить информацию о работе операторов.

Оператор	Действия
+	Если оба аргумента — объекты, создать копию первого объекта и добавить в нее ключи из второго (с заменой). Если оба аргумента — числа, сложить как числа. В противном случае, оба операнда приводятся к строке и складываются как строки.
Другие арифметические операторы	Оба операнда приводятся к числу, и выполняется соответствующая операция. Для битовых операций операнды дополнительно приводятся к `int`.
Операторы сравнения	Если сравниваются две строки или два числа, они сравниваются напрямую. Если сравниваются строка и число, и строка является корректной записью числа, строка приводится к числу. В противном случае возвращается ошибка `Comparing values of different or unsupported types`.
Приведение к строке	Числа и строки приводятся как в JavaScript. Объекты приводятся как перечисление значений через запятую, в порядке следования ключей. `false` и `null` приводятся как `""`, `true` приводится как `"1"`.
Приведение к числу	Если аргумент — строка, являющаяся корректной записью числа, возвращается число. В противном случае возвращается ошибка `Numeric arguments expected`.

При операциях с числами (кроме битовых), если операнды — int и double, int приводится к double. Если оба операнда — int, производится операция над знаковыми 32-битными целыми числами (с переполнением).

Tags:

Hubs: