непрозрачные константы на C++ (морф)

[salsa20]

Вот читаю для саморазвития маты с researchgate(если кому нужно оттуда дёрнуть инфо пишите, есть акк) и стало интересно
как это устроено.

можно так морфить код

(AI) Непрозрачные константы на C++ можно реализовать следующим образом:

1. Описать функцию, которая будет возвращать непрозрачную константу:

int get_opaque_const() {
  // код генерации на основе NP-полной задачи 
}

2. Вместо использования обычных констант в коде вызывать эту функцию:

int a = 10;
int b = 15;

int sum = a + b;

// c использованием непрозрачной константы
int a = 10;
int b = 15;

int opaque_const = get_opaque_const();

int sum = a ^ opaque_const + b;

3. Реализовать функцию get_opaque_const():

// глобальные переменные для графа и формулы
vector<vector<int>> graph;
vector<Clause> formula;

int get_opaque_const() {

  // генерация графа
  generate_graph(); 

  // проверка свойств графа
  // возврат бита константы
  return get_opaque_bit();

}

int get_opaque_bit() {

  if (check_clique()) {
    return 0;
  } else {
    return 1;
  }

}

Таким образом константа будет вычисляться во время выполнения программы на основе сложных графовых преобразований.

 

[salsa20]

Кодик на визуализацию

// Определяем структуру для представления графа
struct Graph {
    std::vector<std::vector<bool>> adjacencyMatrix;
};

// Функция генерации случайного графа
Graph generateRandomGraph(unsigned numVertices) {
    Graph g;
    // Инициализируем матрицу смежности
    g.adjacencyMatrix.resize(numVertices);

    for (unsigned i = 0; i < numVertices; ++i) {
        g.adjacencyMatrix[i].resize(numVertices);

        for (unsigned j = 0; j < numVertices; ++j) {
            if (i == j)
                g.adjacencyMatrix[i][j] = false;
            else
                g.adjacencyMatrix[i][j] = rand() % 2; // случайное ребро
        }
    }

    return g;
}

// Проверка наличия k-клики в графе
bool hasKClique(const Graph& g, unsigned k) {
    // алгоритм проверки k-клики    
}

// Генерация непрозрачной константы
uint32_t generateOpaqueConstant(unsigned numBits) {
    uint32_t constant = 0;

    for (unsigned i = 0; i < numBits; ++i) {
        // 1. Генерируем случайный граф
        Graph g = generateRandomGraph(10);

        // 2. Ищем k-клику (k = 3)
        bool hasClique = hasKClique(g, 3);
       
        // 3. Устанавливаем бит в константе
        if (!hasClique)
            constant |= (1 << i);
    }

    return constant;
}

Данный код демонстрирует основную идею метода.

 

[salsa20]

Пишу пока реализацию, можете оценить кодес

#define VARS_COUNT 5
#define SUBSET_SIZE 5

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <Windows.h>
using namespace std;

map<int, int> vertexToLiteral;

struct Clause : std::vector<int> { };


int getRandomLiteral(int numVars) {

    // Литерал - переменная или ее отрицание
    auto ran = rand();
    int var = ran % numVars + 1;
    bool positive = ran % 2 == 0;

    if (positive)
        return var;
    else
        return -var;
}
struct Graph {

    struct Edge {
        int from;
        int to;
    };

    vector<int> getRandomVerticesSubset(int subsetSize) {

        vector<int> subset;
        vector<int> vertices;

        // Заполняем массив всех вершин
        for (int v = 0; v < adjList.size(); v++) {
            vertices.push_back(v);
        }

        // Перемешиваем случайным образом
        random_shuffle(vertices.begin(), vertices.end());

        // Берем первые subsetSize вершин
        // как случайное подмножество
        for (int i = 0; i < subsetSize; i++) {
            subset.push_back(vertices[i]);
        }

        return subset;
    }

    std::vector<std::vector<int>> adjList;
    std::vector<Edge> edges;

    void addVertex() {
        adjList.emplace_back();
    }

    void removeVertex(int v) {
        adjList.erase(adjList.begin() + v);
        // удалить ребра связанные с v
    }

    void addEdge(int from, int to) {

        if (from == adjList.size()) {
            addVertex();
            from = adjList.size() - 1;
        }

        if (to == adjList.size()) {
            addVertex();
            to = adjList.size() - 1;
        }

        adjList[to].push_back(from);

        // Логгирование добавленного ребра
        std::cout << "Added Edge: (" << from << " -> " << to << ")" << std::endl;
    }



    void removeEdge(int from, int to) {
        // удалить ребро из списков смежности
        // и из массива ребер edges
    }

    std::vector<int> getAdj(int v) {
        return adjList[v];
    }

    bool hasEdge(int from, int to) {
        // Проходим по списку смежности вершины from
        for (int neighbor : adjList[from]) {

            // Если обнаружили в нем вершину to - значит ребро есть
            if (neighbor == to) {
                return true;
            }
        }

        // Не нашли to среди соседей from - ребра нет
        return false;
    }

    int getVerticesCount() {
        return adjList.size();
    }

};


int getVertexByLiteral(int literal) {
    for (int vertex = 0; vertex < vertexToLiteral.size(); vertex++) {
        if (vertexToLiteral[vertex] == literal)
            return vertex;
    }
}

Graph reductionToGraph(const vector<Clause>& clauses) {

    // Создаем граф и резервируем память сразу под нужное количество вершин
    Graph graph;
    int verticesCount = 3 * clauses.size();
    graph.adjList.reserve(verticesCount);
    for (int i = 0; i < verticesCount; i++) {
        graph.addVertex();
    }

    // Проходим по клаузам и литералам
    for (int clauseId = 0; clauseId < clauses.size(); clauseId++) {
        const auto& clause = clauses[clauseId];

        for (int literalId = 0; literalId < 3; literalId++) {
            int vertex = clauseId * 3 + literalId; // Индекс вершины   
            int literal = clause[literalId];

            // Сопоставляем вершину и литерал
            vertexToLiteral[vertex] = literal;
        }
    }

    // Соединяем ребрами литералы из разных
    // клауз, которые могут быть одновременно истинными
    for (int i = 0; i < clauses.size(); i++) {
        const auto& clause1 = clauses[i];

        for (int j = i + 1; j < clauses.size(); j++) {
            const auto& clause2 = clauses[j];

            for (int literal1 : clause1) {
                for (int literal2 : clause2) {
                    if (literal1 != -literal2) {
                        graph.addEdge(getVertexByLiteral(literal1),
                            getVertexByLiteral(literal2));
                    }
                }
            }
        }
    }

    return graph;
}

vector<Clause> generateHard3SATFormula(int numVars) {

    vector<Clause> clauses;

    // Для сложных формул отношение числа клауз
    // к числу переменных должно быть 4.2 - 5.0
    int numClauses = (int)(4.5 * numVars);

    std::cout << "Generating 3SAT Formula:" << std::endl;
    std::cout << "Number of Variables: " << numVars << std::endl;
    std::cout << "Number of Clauses: " << numClauses << std::endl;

    for (int i = 0; i < numClauses; i++) {
        Clause clause;

        // В каждой клаузе 3 случайные литерала
        clause.push_back(getRandomLiteral(numVars));
        clause.push_back(getRandomLiteral(numVars));
        clause.push_back(getRandomLiteral(numVars));

        clauses.push_back(clause);

        // Выводим информацию о каждой сгенерированной клаузе
        std::cout << "Clause " << (i + 1) << ": ";
        for (int literal : clause) {
            std::cout << literal << " ";
        }
        std::cout << std::endl;
    }

    // Перемешиваем клаузы 
    random_shuffle(clauses.begin(), clauses.end());

    return clauses;
}



DWORD generateOpaqueConstant() {

    // Генерируем сложную формулу 3SAT
    vector<Clause> clauses = generateHard3SATFormula(VARS_COUNT);

    // Преобразуем ее в граф
    Graph graph = reductionToGraph(clauses);

    // Выводим информацию о графе в лог
    std::cout << "Graph Information:" << std::endl;
    std::cout << "Number of Vertices: " << graph.getVerticesCount() << std::endl;

    // Выбираем случайное подмножество вершин
    vector<int> vertices = graph.getRandomVerticesSubset(SUBSET_SIZE);

    // Выводим информацию о выбранном подмножестве в лог
    std::cout << "Selected Subset of Vertices:" << std::endl;
    for (int vertex : vertices) {
        std::cout << vertex << " ";
    }
    std::cout << std::endl;

    // Проверяем, является ли оно кликой
    bool isClique = true;
    for (int i = 0; i < vertices.size(); i++) {
        for (int j = i + 1; j < vertices.size(); j++) {
            if (!graph.hasEdge(vertices[i], vertices[j])) {
                isClique = false;
                break;
            }
        }
    }

    // Выводим информацию о том, является ли подмножество кликой
    std::cout << "Is Subset a Clique? " << (isClique ? "Yes" : "No") << std::endl;

    // Формируем непрозрачную константу
    // на основе свойств подмножества вершин и графа
    DWORD opaque = 0;
    if (!isClique) {
        opaque |= 0x1;
    }

    opaque <<= 15;
    opaque |= graph.getVerticesCount() ^ SUBSET_SIZE;

    return opaque;
}
int main()
{
    auto x = generateOpaqueConstant();
    std::cout << "Hello World!\n";
}

выводит

Generating 3SAT Formula:
Number of Variables: 5
Number of Clauses: 22
Clause 1: -2 -3 5
Clause 2: 1 -5 5
Clause 3: 4 4 3
Clause 4: 5 -1 -1
Clause 5: -2 -3 -2
Clause 6: -2 -1 3
Clause 7: -3 2 -2
Clause 8: 5 3 -4
Clause 9: 3 3 -2
Clause 10: 2 4 -1
Clause 11: -3 2 -2
Clause 12: 4 -5 3
Clause 13: -3 -5 -1
Clause 14: 5 -4 -2
Clause 15: 3 -4 -4
Clause 16: 5 -2 -2
Clause 17: -4 4 -3
Clause 18: 5 3 -3
Clause 19: -3 -5 -4
Clause 20: -2 -5 4
Clause 21: 2 -1 1
Clause 22: 3 4 2
Graph Information:
Number of Vertices: 66
Selected Subset of Vertices:
45 60 54 14 27
Is Subset a Clique? No

 

[drpalpatine]

Automatic generation of opaque constants based on the k-clique problem for resilient data obfuscation

Data obfuscations are program transformations used to complicate program understanding and conceal actual values of program variables. The possibility to hide constant values is a basic building block of several obfuscation techniques. For example, in XOR Masking a constant mask is used to...

ieeexplore.ieee.org

Experimental assessment of XOR-Masking data obfuscation based on K-Clique opaque constants

Data obfuscations are program transformations used to complicate program understanding and conceal actual values of program variables. The possibility…

www.sciencedirect.com

you can find the free pdf on the researchgate + scihub

 

[drpalpatine]

// Для сложных формул отношение числа клауз // к числу переменных должно быть 4.2 - 5.0 int numClauses = (int)(4.5 * numVars);

this is from a old Bart Selman paper --> but use a SAT solver to check unsatisifbilty --> generally at first try with high number of propsitional vawriables
B. Selman, D. G. Mitchell, and H. J. Levesque, “Generating hard satisfiability problems,” Artificial intelligence, vol. 81, no. 1, pp. 17–29, 1996.

from pysat.solvers import Solver

def check_unsatisfiability(clauses: List[List[int]], assumptions: List[int] = []) -> bool:
    with Solver() as solver:
        solver.append_formula(clauses)
        unique_assumptions = list(set(assumptions))
        return not solver.solve(assumptions=unique_assumptions)

def generate_3sat(n: int, k: int) -> List[List[int]]:
    """   
    param-->
    - n: propositional variables
    - k: clauses

    ret-->
    - list of clauses--> list of 3 literals
    """
    variables = list(range(1, n + 1))
    clauses = []

    # random generate k clauses
    for _ in range(k):
        clause = random.sample(variables, 3)
        clause_literals = []

        # random negate some literals inside clause
        for var in clause:
            if random.random() < 0.5:
                clause_literals.append(-var)
            else:
                clause_literals.append(var)

        clauses.append(clause_literals)

    return clauses

 

[salsa20]

https://www.researchgate.net/publication/315638749_Automatic_generation_of_opaque_constants_based_on_the_k-clique_problem_for_resilient_data_obfuscation

Вот в тему.

 

[salsa20]

GitHub - 00max09/CUDA-k-Clique-Counter: k Clique Counting CUDA implementation

k Clique Counting CUDA implementation. Contribute to 00max09/CUDA-k-Clique-Counter development by creating an account on GitHub.

github.com

gpu ускорение

upd ; GPU acceleration of local search for maximum weight cliques

Описание для наших пацанов

В данной научной статье представлен эвристический алгоритм GPU Local Search (GPULS) для решения задачи о максимальном весовом клике в огромных графах на гибридной CPU-GPU архитектуре.

Основные моменты:

1. Предложены две новые структуры окрестностей для задачи о максимальном весовом клике - N1 и N2. Они исследуются с помощью эффективной процедуры, подходящей для реализации на массивно-параллельной GPU архитектуре.

2. Алгоритм GPULS основан на многостартовом локальном поиске. Он итеративно исследует окрестности N1 и N2 с использованием tabu search и first-improvement подхода соответственно.

3. Даже при выполнении на CPU GPULS превосходит известные эвристики по времени и качеству решения.

4. Гибридная реализация CPU-GPU достигает ускорения до 12 раз по сравнению с чисто CPU версией. Ускорение растет с размером задачи.

5. Результаты продемонстрированы на реальных графах с миллионами ребер и вершин. GPULS переигрывает лучший известный точный алгоритм на массивных не разреженных графах.

Таким образом, в работе предложен новый перспективный подход к решению задачи о максимальном весовом клике на огромных графах с использованием вычислительной мощности GPU.

 

[salsa20]

Вообщем работает

Graph Information:
Number of Vertices: 66
Selected Subset of Vertices:
33 36 45 11 50 4 16 60 40 30
Is Subset a Clique? No
-----------------------------------
Original a: 1337
Opaque Constant: 32840
Encrypted a: 34161
Decrypted a: 1337

#define VARS_COUNT 5
#define SUBSET_SIZE 10

#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <algorithm>
#include <Windows.h>
using namespace std;

map<int, int> vertexToLiteral;

struct Clause : std::vector<int> { };

static bool isSatisfiable(const std::vector<Clause>& clauses) {
    std::vector<bool> model(clauses.size(), false);

    while (true) {
        bool conflict = false;

        for (const auto& clause : clauses) {
            bool clause_sat = false;

            for (int lit : clause) {
                int var = abs(lit);

                if (lit > 0 && model[var - 1] ||
                    lit < 0 && !model[var - 1])
                {
                    clause_sat = true;
                    break;
                }
            }

            if (!clause_sat) {
                conflict = true;
                break;
            }
        }

        if (!conflict) {
            return true;
        }

        bool model_fixed = false;

        for (const auto& clause : clauses) {
            for (int lit : clause) {
                int var = abs(lit);

                if (lit > 0 && !model[var - 1]) {
                    model[var - 1] = true;
                    model_fixed = true;
                    break;
                }

                if (lit < 0 && model[var - 1]) {
                    model[var - 1] = false;
                    model_fixed = true;
                    break;
                }
            }

            if (model_fixed) {
                break;
            }
        }

        if (!model_fixed) {
            return false;
        }
    }
}


int getRandomLiteral(int numVars) {

    // Литерал - переменная или ее отрицание
    auto ran = rand();
    int var = ran % numVars + 1;
    bool positive = ran % 2 == 0;

    if (positive)
        return var;
    else
        return -var;
}
struct Graph {
    struct Edge {
        int from;
        int to;
        int multiplicity; // количество повторов ребра
    };
    // Функция для поиска максимальной клики
    std::vector<int> findMaxClique() {
        std::vector<int> currentClique;
        std::vector<int> maxClique;
        std::vector<bool> candidates(getVerticesCount(), true);

        findMaxCliqueRecursive(currentClique, maxClique, candidates);

        return maxClique;
    }
    vector<int> getRandomVerticesSubset(int subsetSize) {

        vector<int> subset;
        vector<int> vertices;

        // Заполняем массив всех вершин
        for (int v = 0; v < adjList.size(); v++) {
            vertices.push_back(v);
        }

        // Перемешиваем вершины в случайном порядке
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(vertices.begin(), vertices.end(), g);

        // Берем первые subsetSize вершин
        // как случайное подмножество
        for (int i = 0; i < subsetSize; i++) {
            subset.push_back(vertices[i]);
        }

        return subset;
    }

    std::vector<std::vector<int>> adjList;
    std::vector<Edge> edges;

    void addVertex() {
        adjList.emplace_back();
    }

    void removeVertex(int v) {

        // удаляем вершину из списка смежности
        adjList.erase(adjList.begin() + v);

        // удаляем ребра из массива edges
        for (int i = 0; i < edges.size(); i++) {
            if (edges[i].from == v || edges[i].to == v) {
                edges.erase(edges.begin() + i);
                i--;
            }
        }

        // удаляем ребра из списков смежности
        for (auto& neighbors : adjList) {
            neighbors.erase(
                remove(neighbors.begin(), neighbors.end(), v),
                neighbors.end()
            );
        }

    }


    //поддержка мультиграфов и петель
    void addEdge(int from, int to) {

        // проверяем на петлю
        if (from == to) {

            // ищем петлю в списке ребер
            bool loopExists = false;
            for (Edge& edge : edges) {
                if (edge.from == from && edge.to == to) {
                    edge.multiplicity++;
                    loopExists = true;
                    break;
                }
            }

            // если петли еще нет - добавляем
            if (!loopExists) {
                Edge edge{};
                edge.from = from;
                edge.to = to;
                edge.multiplicity = 1;
                edges.push_back(edge);
            }

            return;
        }

        // ищем обычное ребро в списке
        for (Edge& edge : edges) {
            if (edge.from == from && edge.to == to) {
                edge.multiplicity++;
                return;
            }
        }

        // не нашли ребро - добавляем новое
        Edge edge{};
        edge.from = from;
        edge.to = to;
        edge.multiplicity = 1;
        edges.push_back(edge);

    }



    void removeEdge(int from, int to) {
        // удалить ребро из списков смежности
        // и из массива ребер edges
    }

    std::vector<int> getAdj(int v) {
        return adjList[v];
    }

    bool hasEdge(int from, int to) {
        // Проходим по списку смежности вершины from
        for (int neighbor : adjList[from]) {

            // Если обнаружили в нем вершину to - значит ребро есть
            if (neighbor == to) {
                return true;
            }
        }

        // Не нашли to среди соседей from - ребра нет
        return false;
    }

    int getVerticesCount() {
        return adjList.size();
    }
    private:
        void findMaxCliqueRecursive(std::vector<int>& currentClique, std::vector<int>& maxClique, std::vector<bool>& candidates) {
            if (candidates.empty()) {
                if (currentClique.size() > maxClique.size()) {
                    maxClique = currentClique;
                }
                return;
            }

            for (int i = 0; i < candidates.size(); ++i) {
                if (!candidates[i]) continue;

                // Проверяем, можно ли добавить вершину i в текущую клику
                bool canAdd = true;
                for (int vertex : currentClique) {
                    if (!hasEdge(i, vertex)) {
                        canAdd = false;
                        break;
                    }
                }

                if (canAdd) {
                    currentClique.push_back(i);
                    std::vector<bool> newCandidates = candidates;
                    for (int neighbor : getAdj(i)) {
                        newCandidates[neighbor] = false;
                    }
                    findMaxCliqueRecursive(currentClique, maxClique, newCandidates);
                    currentClique.pop_back();
                }
            }
        }

};


int getVertexByLiteral(int literal) {
    for (int vertex = 0; vertex < vertexToLiteral.size(); vertex++) {
        if (vertexToLiteral[vertex] == literal)
            return vertex;
    }
}

Graph reductionToGraph(const vector<Clause>& clauses) {

    // Создаем граф и резервируем память сразу под нужное количество вершин
    Graph graph;
    int verticesCount = 3 * clauses.size();
    graph.adjList.reserve(verticesCount);
    for (int i = 0; i < verticesCount; i++) {
        graph.addVertex();
    }

    // Проходим по клаузам и литералам
    for (int clauseId = 0; clauseId < clauses.size(); clauseId++) {
        const auto& clause = clauses[clauseId];

        for (int literalId = 0; literalId < 3; literalId++) {
            int vertex = clauseId * 3 + literalId; // Индекс вершины   
            int literal = clause[literalId];

            // Сопоставляем вершину и литерал
            vertexToLiteral[vertex] = literal;
        }
    }

    // Соединяем ребрами литералы из разных
    // клауз, которые могут быть одновременно истинными
    for (int i = 0; i < clauses.size(); i++) {
        const auto& clause1 = clauses[i];

        for (int j = i + 1; j < clauses.size(); j++) {
            const auto& clause2 = clauses[j];

            for (int literal1 : clause1) {
                for (int literal2 : clause2) {
                    if (literal1 != -literal2) {
                        graph.addEdge(getVertexByLiteral(literal1),
                            getVertexByLiteral(literal2));
                    }
                }
            }
        }
    }

    return graph;
}
vector<Clause> generateHard3SATFormula(int numVars) {

    vector<Clause> clauses;

    // То же самое количество ограничений
    int numClauses = (int)(4.5 * numVars);

    //while (true) {
        clauses.clear();

        for (int i = 0; i < numClauses; i++) {
            Clause clause;

            // В каждом ограничении 3 случайных литерала
            clause.push_back(getRandomLiteral(numVars));
            clause.push_back(getRandomLiteral(numVars));
            clause.push_back(getRandomLiteral(numVars));

            clauses.push_back(clause);
        }

    /*    if (!isSatisfiable(clauses)) {
            break;
        }
    }*/

    return clauses;
}

vector<Clause> generateHard3SATFormulaOld(int numVars) {

    vector<Clause> clauses;

    // Для сложных формул отношение числа клауз
    // к числу переменных должно быть 4.2 - 5.0
    int numClauses = (int)(4.5 * numVars);

    std::cout << "Generating 3SAT Formula:" << std::endl;
    std::cout << "Number of Variables: " << numVars << std::endl;
    std::cout << "Number of Clauses: " << numClauses << std::endl;

    for (int i = 0; i < numClauses; i++) {
        Clause clause;

        // В каждой клаузе 3 случайные литерала
        clause.push_back(getRandomLiteral(numVars));
        clause.push_back(getRandomLiteral(numVars));
        clause.push_back(getRandomLiteral(numVars));

        clauses.push_back(clause);

        // Выводим информацию о каждой сгенерированной клаузе
        std::cout << "Clause " << (i + 1) << ": ";
        for (int literal : clause) {
            std::cout << literal << " ";
        }
        std::cout << std::endl;
    }

    // Перемешиваем клаузы 
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(clauses.begin(), clauses.end(), g);
    return clauses;
}

DWORD generateOpaqueConstant2() {
    // Генерируем сложную формулу 3SAT
    vector<Clause> clauses = generateHard3SATFormula(VARS_COUNT);

    // Преобразуем ее в граф
    Graph graph = reductionToGraph(clauses);

    // Находим максимальную клику в графе
    vector<int> maxClique = graph.findMaxClique();

    // Выводим информацию о максимальной клике в лог
    std::cout << "Max Clique Vertices:" << std::endl;
    for (int vertex : maxClique) {
        std::cout << vertex << " ";
    }
    std::cout << std::endl;

    // Формируем непрозрачную константу
    // на основе свойств максимальной клики и графа
    DWORD opaque = 0;
    if (maxClique.size() != graph.getVerticesCount()) {
        opaque |= 0x1;
    }

    opaque <<= 15;
    opaque |= graph.getVerticesCount() ^ SUBSET_SIZE;

    return opaque;
}


DWORD generateOpaqueConstant() {

    // Генерируем сложную формулу 3SAT
    vector<Clause> clauses = generateHard3SATFormula(VARS_COUNT);

    // Преобразуем ее в граф
    Graph graph = reductionToGraph(clauses);

    // Выводим информацию о графе в лог
    std::cout << "Graph Information:" << std::endl;
    std::cout << "Number of Vertices: " << graph.getVerticesCount() << std::endl;

    // Выбираем случайное подмножество вершин
    vector<int> vertices = graph.getRandomVerticesSubset(SUBSET_SIZE);

    // Выводим информацию о выбранном подмножестве в лог
    std::cout << "Selected Subset of Vertices:" << std::endl;
    for (int vertex : vertices) {
        std::cout << vertex << " ";
    }
    std::cout << std::endl;

    // Проверяем, является ли оно кликой
    bool isClique = true;
    for (int i = 0; i < vertices.size(); i++) {
        for (int j = i + 1; j < vertices.size(); j++) {
            if (!graph.hasEdge(vertices[i], vertices[j])) {
                isClique = false;
                break;
            }
        }
    }

    // Выводим информацию о том, является ли подмножество кликой
    std::cout << "Is Subset a Clique? " << (isClique ? "Yes" : "No") << std::endl;

    // Формируем непрозрачную константу
    // на основе свойств подмножества вершин и графа
    DWORD opaque = 0;
    if (!isClique) {
        opaque |= 0x1;
    }

    opaque <<= 15;
    opaque |= graph.getVerticesCount() ^ SUBSET_SIZE;

    return opaque;
}

std::vector<std::vector<int>> gen3sat(int n, int k) {
    std::vector<int> variables(n);
    for (int i = 0; i < n; i++) {
        variables[i] = i + 1;
    }

    std::vector<std::vector<int>> clauses;
    std::default_random_engine generator;
    std::uniform_real_distribution<double> distribution(0.0, 1.0);

    for (int i = 0; i < k; i++) {
        std::vector<int> clause;
        std::sample(variables.begin(), variables.end(), std::back_inserter(clause), 3, generator);

        for (int& lit : clause) {
            if (distribution(generator) < 0.5) {
                lit = -lit;
            }
        }

        clauses.push_back(clause);
    }

    return clauses;
}

DWORD generateGaranteeOpaqueConstant() {
    // Генерируем сложную формулу 3SAT
    vector<Clause> clauses = generateHard3SATFormula(VARS_COUNT);

    // Преобразуем ее в граф
    Graph graph = reductionToGraph(clauses);

    // Выводим информацию о графе в лог
    std::cout << "Graph Information:" << std::endl;
    std::cout << "Number of Vertices: " << graph.getVerticesCount() << std::endl;

    // Формируем непрозрачную константу на основе свойств подмножества вершин и графа
    DWORD opaque = 0;
    opaque <<= 15;
    opaque |= graph.getVerticesCount() ^ SUBSET_SIZE;

    return opaque;
}

int main()
{
    int a = 1337;
    int opaque_const = generateOpaqueConstant();

    std::cout << "-----------------------------------" << std::endl;

    std::cout << "Original a: " << a << std::endl;
    std::cout << "Opaque Constant: " << opaque_const << std::endl;

    // Применяем операцию XOR шифрования к значению 'a' с использованием непрозрачной константы
    int encrypted_a = a ^ opaque_const;
    std::cout << "Encrypted a: " << encrypted_a << std::endl;

    // Для дешифровки просто применяем XOR снова к зашифрованному значению
    int decrypted_a = encrypted_a ^ opaque_const;
    std::cout << "Decrypted a: " << decrypted_a << std::endl;

    return 0;

}

 

[salsa20]

если увеличивать значения то растет и время вычисления

#define VARS_COUNT 66
#define SUBSET_SIZE 66

 

[salsa20]

Как по мне техника замечательная потому что для крипта или шифрования вам нужно просто хранить дату для непрозрачной константы(сформированную уже на этапе защиты) и зашифрованную переменную. Xor выдаст оригинал.

 

[secflag]

Что обозначает "непрозрачная константа" в морфинге?

 

[coder]

Что обозначает "непрозрачная константа" в морфинге?

Opaque predicate - Wikipedia

en.wikipedia.org

 

[salsa20]

Что обозначает "непрозрачная константа" в морфинге?

Непрозрачные константы (opaque constants) в морфинге XOR обозначают константы, значения которых скрыты в программе для затруднения понимания и анализа кода.

В частности, в преобразовании XOR маскирования используется константа-маска p для кодирования данных путем вычисления XOR с чистым значением x:

e(x) = x ^ p

Где e(x) - зашифрованное значение, x - исходное чистое значение, p - константа-маска.

Чтобы сделать анализ и взлом такого шифрования более сложным, константа-маска p может быть скрыта и вычисляться во время выполнения программы, вместо хранения явно в коде. Такая константа-маска и называется непрозрачной константой.

Для этого непрозрачная константа может вычисляться на основе некоторой сложной задачи NP-полной, например задачи о клике. Тогда при статическом анализе программы атакующему придется решать эту сложную задачу, чтобы определить фактическое значение константы p и взломать шифрование.

Таким образом, непрозрачные константы усложняют статический анализ и взлом преобразований морфинга вроде XOR маскирования.

 

[pentesterMaster]

Пишу пока реализацию, можете оценить кодес

#define VARS_COUNT 5
#define SUBSET_SIZE 5

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <Windows.h>
using namespace std;

map<int, int> vertexToLiteral;

struct Clause : std::vector<int> { };


int getRandomLiteral(int numVars) {

    // Литерал - переменная или ее отрицание
    auto ran = rand();
    int var = ran % numVars + 1;
    bool positive = ran % 2 == 0;

    if (positive)
        return var;
    else
        return -var;
}
struct Graph {

    struct Edge {
        int from;
        int to;
    };

    vector<int> getRandomVerticesSubset(int subsetSize) {

        vector<int> subset;
        vector<int> vertices;

        // Заполняем массив всех вершин
        for (int v = 0; v < adjList.size(); v++) {
            vertices.push_back(v);
        }

        // Перемешиваем случайным образом
        random_shuffle(vertices.begin(), vertices.end());

        // Берем первые subsetSize вершин
        // как случайное подмножество
        for (int i = 0; i < subsetSize; i++) {
            subset.push_back(vertices[i]);
        }

        return subset;
    }

    std::vector<std::vector<int>> adjList;
    std::vector<Edge> edges;

    void addVertex() {
        adjList.emplace_back();
    }

    void removeVertex(int v) {
        adjList.erase(adjList.begin() + v);
        // удалить ребра связанные с v
    }

    void addEdge(int from, int to) {

        if (from == adjList.size()) {
            addVertex();
            from = adjList.size() - 1;
        }

        if (to == adjList.size()) {
            addVertex();
            to = adjList.size() - 1;
        }

        adjList[to].push_back(from);

        // Логгирование добавленного ребра
        std::cout << "Added Edge: (" << from << " -> " << to << ")" << std::endl;
    }



    void removeEdge(int from, int to) {
        // удалить ребро из списков смежности
        // и из массива ребер edges
    }

    std::vector<int> getAdj(int v) {
        return adjList[v];
    }

    bool hasEdge(int from, int to) {
        // Проходим по списку смежности вершины from
        for (int neighbor : adjList[from]) {

            // Если обнаружили в нем вершину to - значит ребро есть
            if (neighbor == to) {
                return true;
            }
        }

        // Не нашли to среди соседей from - ребра нет
        return false;
    }

    int getVerticesCount() {
        return adjList.size();
    }

};


int getVertexByLiteral(int literal) {
    for (int vertex = 0; vertex < vertexToLiteral.size(); vertex++) {
        if (vertexToLiteral[vertex] == literal)
            return vertex;
    }
}

Graph reductionToGraph(const vector<Clause>& clauses) {

    // Создаем граф и резервируем память сразу под нужное количество вершин
    Graph graph;
    int verticesCount = 3 * clauses.size();
    graph.adjList.reserve(verticesCount);
    for (int i = 0; i < verticesCount; i++) {
        graph.addVertex();
    }

    // Проходим по клаузам и литералам
    for (int clauseId = 0; clauseId < clauses.size(); clauseId++) {
        const auto& clause = clauses[clauseId];

        for (int literalId = 0; literalId < 3; literalId++) {
            int vertex = clauseId * 3 + literalId; // Индекс вершины  
            int literal = clause[literalId];

            // Сопоставляем вершину и литерал
            vertexToLiteral[vertex] = literal;
        }
    }

    // Соединяем ребрами литералы из разных
    // клауз, которые могут быть одновременно истинными
    for (int i = 0; i < clauses.size(); i++) {
        const auto& clause1 = clauses[i];

        for (int j = i + 1; j < clauses.size(); j++) {
            const auto& clause2 = clauses[j];

            for (int literal1 : clause1) {
                for (int literal2 : clause2) {
                    if (literal1 != -literal2) {
                        graph.addEdge(getVertexByLiteral(literal1),
                            getVertexByLiteral(literal2));
                    }
                }
            }
        }
    }

    return graph;
}

vector<Clause> generateHard3SATFormula(int numVars) {

    vector<Clause> clauses;

    // Для сложных формул отношение числа клауз
    // к числу переменных должно быть 4.2 - 5.0
    int numClauses = (int)(4.5 * numVars);

    std::cout << "Generating 3SAT Formula:" << std::endl;
    std::cout << "Number of Variables: " << numVars << std::endl;
    std::cout << "Number of Clauses: " << numClauses << std::endl;

    for (int i = 0; i < numClauses; i++) {
        Clause clause;

        // В каждой клаузе 3 случайные литерала
        clause.push_back(getRandomLiteral(numVars));
        clause.push_back(getRandomLiteral(numVars));
        clause.push_back(getRandomLiteral(numVars));

        clauses.push_back(clause);

        // Выводим информацию о каждой сгенерированной клаузе
        std::cout << "Clause " << (i + 1) << ": ";
        for (int literal : clause) {
            std::cout << literal << " ";
        }
        std::cout << std::endl;
    }

    // Перемешиваем клаузы
    random_shuffle(clauses.begin(), clauses.end());

    return clauses;
}



DWORD generateOpaqueConstant() {

    // Генерируем сложную формулу 3SAT
    vector<Clause> clauses = generateHard3SATFormula(VARS_COUNT);

    // Преобразуем ее в граф
    Graph graph = reductionToGraph(clauses);

    // Выводим информацию о графе в лог
    std::cout << "Graph Information:" << std::endl;
    std::cout << "Number of Vertices: " << graph.getVerticesCount() << std::endl;

    // Выбираем случайное подмножество вершин
    vector<int> vertices = graph.getRandomVerticesSubset(SUBSET_SIZE);

    // Выводим информацию о выбранном подмножестве в лог
    std::cout << "Selected Subset of Vertices:" << std::endl;
    for (int vertex : vertices) {
        std::cout << vertex << " ";
    }
    std::cout << std::endl;

    // Проверяем, является ли оно кликой
    bool isClique = true;
    for (int i = 0; i < vertices.size(); i++) {
        for (int j = i + 1; j < vertices.size(); j++) {
            if (!graph.hasEdge(vertices[i], vertices[j])) {
                isClique = false;
                break;
            }
        }
    }

    // Print information about whether the subset is a clique
    std::cout << "Is Subset a Clique? " << (isClique ? "Yes" : "No") << std::endl;

    // Form an opaque constant
    // based on the properties of a subset of vertices and the graph
    DWORD opaque = 0;
    if (!isClique) {
        opaque |= 0x1;
    }

    opaque <<= 15;
    opaque |= graph.getVerticesCount() ^SUBSET_SIZE;

    return opaque;
}
int main()
{
    auto x = generateOpaqueConstant();
    std::cout << "Hello World!\n";
}

displays

Bro you are a good developer ... Wish to Team up with you...